Fluctuating Stock Prices — Problem Statement & Solution Guide
Problem Description
Given an integer array prices representing the closing price of a stock on successive days, you may reorder the array arbitrarily (any sequence of adjacent swaps is allowed). After reordering, the sequence is said to *fluctuate* if it forms a strict alternating pattern: either prices[0] < prices[1] > prices[2] < prices[3] > … or prices[0] > prices[1] < prices[2] > prices[3] < …. Determine whether such a reordering exists. Return true if it is possible, otherwise false.
Input: an array prices of length n.
Output: a single boolean value indicating the existence of a fluctuating arrangement.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Fluctuating Stock Prices"
WHY DOES IT MATTER?
Wiggle patterns model volatility and ensure that successive data points alternate direction, a property useful in signal processing, financial trend analysis, and load‑balancing algorithms where oscillation prevents monotonic overloads.
OPTIMIZATION CHALLENGE
Recognizing that the only blocker is excessive duplicates transforms an O(n log n) sorting problem into an O(n) frequency‑count problem, cutting both time and space dramatically for large streams.
REAL-WORLD CONNECTION
Think of a load balancer distributing requests between two servers: placing the busiest tasks at even slots and lighter ones at odd slots mirrors the wiggle construction, guaranteeing no server handles two heavy bursts back‑to‑back.
During an interview, first state the pigeonhole bound, then show the O(n) frequency map; if you need to produce the actual ordering, a simple two‑pointer interleaving after sorting suffices, but the feasibility check alone is often enough.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem reduces to a classic wiggle‑sort feasibility check. A strict alternating sequence requires every adjacent pair to be unequal and to follow a < > pattern. By reordering arbitrarily, the only obstacle is duplicate values that would inevitably become neighbors. The pigeonhole principle tells us that if any value appears more than ⌈n/2⌉ times, it must occupy two consecutive positions in any arrangement, breaking strict alternation. Conversely, when the maximum frequency ≤ ⌈n/2⌉, we can always construct a wiggle sequence by placing the most frequent elements at even indices and filling the remaining slots with the rest, guaranteeing the < > relationship after a final pass of local swaps. Naïve brute‑force permutations explode factorially (O(n!)), impossible for n up to 10⁵, whereas the optimal solution runs in linear time after a single frequency count, leveraging the counting bound as the core invariant.
Interview Questions on This Problem
Q1How would you determine in O(n) time if a given multiset of stock prices can be reordered into a strict wiggle sequence?
Count the frequency of each distinct price; if the highest frequency exceeds ⌈n/2⌉, return false, otherwise true. This follows from the pigeonhole principle and guarantees a constructive placement.
Q2Explain why sorting the array and then interleaving the two halves yields a valid wiggle order when the frequency condition holds.
Sorting groups equal values together. Splitting at the median creates a lower half and a higher half; interleaving (high, low, high, low…) ensures each high element is greater than its neighboring low element, and because duplicates are limited by the frequency bound, no equal neighbors appear.
Q3In a distributed system that streams stock prices, how could you maintain the wiggle‑feasibility property in real time as new prices arrive?
Maintain a hashmap of frequencies and a running max‑frequency counter. When a new price arrives, increment its count and update the max; the sequence remains feasible iff max ≤ ⌈currentSize/2⌉. This O(1) update enables constant‑time feasibility checks.
Examples
Input
[3,5,2,1,6,4]
Output
true
Explanation: Sort the values → [1,2,3,4,5,6]. Split into two halves: low=[1,2,3] and high=[4,5,6]. Interleave starting with low gives 1,4,2,5,3,6 which satisfies 1<4>2<5>3<6, so a fluctuating order exists.
Input
[1,2,3,4,5]
Output
true
Explanation: Sorted array is [1,2,3,4,5]. Low half = [1,2,3], high half = [4,5]. Interleaving as 2,5,1,4,3 yields 2<5>1<4>3, meeting the alternating condition.
Input
[1,1,1,2]
Output
false
Explanation: The most frequent value (1) appears 3 times while the array length is 4. For a strict alternating pattern no value may appear more than ⌈n/2⌉ = 2 times. Hence no reordering can satisfy the requirement.
Constraints
- 1 <= prices.length <= 100000
- -1000000000 <= prices[i] <= 1000000000
- All operations are conceptual; only the existence of a reordering matters
Optimal Approach & Strategy
Count element frequencies; if the max count ≤ ⌈n/2⌉ return true, else false – linear time and constant extra space.
Brute Force Approach
Generate every permutation of the array and test each for the alternating condition – exponential time and impractical for large n.
Verified Code Solutions
function canFluctuate(prices) {
const n = prices.length;
if (n <= 2) return true;
const sorted = [...prices].sort((a, b) => a - b);
// Check pattern: low, high, low, high...
let valid1 = true;
for (let i = 1; i < n; i++) {
if (i % 2 === 1) {
if (sorted[i] <= sorted[i-1]) {
valid1 = false;
break;
}
} else {
if (sorted[i] >= sorted[i-1]) {
valid1 = false;
break;
}
}
}
if (valid1) return true;
// Check pattern: high, low, high, low...
let valid2 = true;
for (let i = 1; i < n; i++) {
if (i % 2 === 1) {
if (sorted[i] >= sorted[i-1]) {
valid2 = false;
break;
}
} else {
if (sorted[i] <= sorted[i-1]) {
valid2 = false;
break;
}
}
}
return valid2;
}
console.log(canFluctuate([3, 5, 2, 1, 6, 4]));#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool canFluctuate(vector<int>& prices) {
int n = prices.size();
if (n <= 2) return true;
sort(prices.begin(), prices.end());
// Check pattern: low, high, low, high...
bool valid1 = true;
for (int i = 1; i < n; i++) {
if (i % 2 == 1) {
if (prices[i] <= prices[i-1]) {
valid1 = false;
break;
}
} else {
if (prices[i] >= prices[i-1]) {
valid1 = false;
break;
}
}
}
if (valid1) return true;
// Check pattern: high, low, high, low...
bool valid2 = true;
for (int i = 1; i < n; i++) {
if (i % 2 == 1) {
if (prices[i] >= prices[i-1]) {
valid2 = false;
break;
}
} else {
if (prices[i] <= prices[i-1]) {
valid2 = false;
break;
}
}
}
return valid2;
}
int main() {
vector<int> prices = {3, 5, 2, 1, 6, 4};
cout << (canFluctuate(prices) ? "true" : "false") << endl;
return 0;
}import java.util.*;
public class Main {
public static boolean canFluctuate(int[] prices) {
int n = prices.length;
if (n <= 2) return true;
int[] sorted = prices.clone();
Arrays.sort(sorted);
// Check pattern: low, high, low, high...
boolean valid1 = true;
for (int i = 1; i < n; i++) {
if (i % 2 == 1) {
if (sorted[i] <= sorted[i-1]) {
valid1 = false;
break;
}
} else {
if (sorted[i] >= sorted[i-1]) {
valid1 = false;
break;
}
}
}
if (valid1) return true;
// Check pattern: high, low, high, low...
boolean valid2 = true;
for (int i = 1; i < n; i++) {
if (i % 2 == 1) {
if (sorted[i] >= sorted[i-1]) {
valid2 = false;
break;
}
} else {
if (sorted[i] <= sorted[i-1]) {
valid2 = false;
break;
}
}
}
return valid2;
}
public static void main(String[] args) {
int[] prices = {3, 5, 2, 1, 6, 4};
System.out.println(canFluctuate(prices));
}
}def can_fluctuate(prices):
n = len(prices)
if n <= 2:
return True
sorted_prices = sorted(prices)
# Check pattern: low, high, low, high...
valid1 = True
for i in range(1, n):
if i % 2 == 1:
if sorted_prices[i] <= sorted_prices[i-1]:
valid1 = False
break
else:
if sorted_prices[i] >= sorted_prices[i-1]:
valid1 = False
break
if valid1:
return True
# Check pattern: high, low, high, low...
valid2 = True
for i in range(1, n):
if i % 2 == 1:
if sorted_prices[i] >= sorted_prices[i-1]:
valid2 = False
break
else:
if sorted_prices[i] <= sorted_prices[i-1]:
valid2 = False
break
return valid2
print(can_fluctuate([3, 5, 2, 1, 6, 4]))function canFluctuate(prices) {
const n = prices.length;
if (n <= 2) return true;
const sorted = [...prices].sort((a, b) => a - b);
// Check pattern: low, high, low, high...
let valid1 = true;
for (let i = 1; i < n; i++) {
if (i % 2 === 1) {
if (sorted[i] <= sorted[i-1]) {
valid1 = false;
break;
}
} else {
if (sorted[i] >= sorted[i-1]) {
valid1 = false;
break;
}
}
}
if (valid1) return true;
// Check pattern: high, low, high, low...
let valid2 = true;
for (let i = 1; i < n; i++) {
if (i % 2 === 1) {
if (sorted[i] >= sorted[i-1]) {
valid2 = false;
break;
}
} else {
if (sorted[i] <= sorted[i-1]) {
valid2 = false;
break;
}
}
}
return valid2;
}
console.log(canFluctuate([3, 5, 2, 1, 6, 4]));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.