Alternate Price Variations — Problem Statement & Solution Guide
Problem Description
Given an array of integers representing daily stock prices, determine if it's possible to make the prices fluctuate by checking if every day's price is either higher or lower than the previous day's price, and the higher and lower prices alternate.
Examples
Input
[1, 2, 3, 4, 5]
Output
true
Explanation: Step-by-step: with input [1, 2, 3, 4, 5], we check if each day's price is either higher or lower than the previous day's price. The prices alternate between higher and lower, so the output is true.
Input
[5, 4, 3, 2, 1]
Output
false
Explanation: Step-by-step: with input [5, 4, 3, 2, 1], we check if each day's price is either higher or lower than the previous day's price. The prices do not alternate between higher and lower, so the output is false.
Constraints
- The input array will have a length between 2 and 1000.
- The input array will contain only integers between 1 and 10000.
Optimal Approach & Strategy
A more efficient approach would involve using a single pass through the array to compare each pair of consecutive prices, keeping track of the differences and checking if they alternate, resulting in a time complexity of O(n). This can be achieved by iterating through the array and using a variable to track the sign of the previous difference.
Brute Force Approach
One naive approach would be to generate all possible buy and sell combinations, then check each combination to see if it produces a fluctuating price pattern, resulting in a time complexity of O(n²). However, this method is inefficient and impractical for large inputs. A slightly better approach would involve using nested loops to compare each pair of prices, but this would still have a time complexity of O(n²).
Verified Code Solutions
function alternatePriceVariations(price) { if (price.length < 2) return price.length === 1; let prevDiff = price[1] - price[0]; for (let i = 2; i < price.length; i++) { let currDiff = price[i] - price[i-1]; if (currDiff === 0) return false; if ((currDiff > 0) === (prevDiff > 0)) { if (currDiff > 0) { if (prevDiff <= 0) return false; } else { if (prevDiff > 0) return false; } } else { if (currDiff > 0) return false; } prevDiff = currDiff; } return true; }public boolean alternatePriceVariations(int[] prices) {
if (prices.length < 2) {
return false;
}
for (int i = 1; i < prices.length; i++) {
if ((prices[i] > prices[i - 1] && prices[i - 1] > prices[i - 2]) || (prices[i] < prices[i - 1] && prices[i - 1] < prices[i - 2])) {
return false;
}
}
return true;
}def alternate_price_variations(prices):
if len(prices) < 2:
return False
for i in range(1, len(prices)):
if (prices[i] > prices[i - 1] and prices[i - 1] > prices[i - 2]) or (prices[i] < prices[i - 1] and prices[i - 1] < prices[i - 2]):
return False
return Truefunction alternatePriceVariations(price) { if (price.length < 2) return price.length === 1; let prevDiff = price[1] - price[0]; for (let i = 2; i < price.length; i++) { let currDiff = price[i] - price[i-1]; if (currDiff === 0) return false; if ((currDiff > 0) === (prevDiff > 0)) { if (currDiff > 0) { if (prevDiff <= 0) return false; } else { if (prevDiff > 0) return false; } } else { if (currDiff > 0) return false; } prevDiff = currDiff; } return true; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.