Stack-Based Approach for Codeforces 1380A — Three Indices Problem Statement
Given a permutation array p of length n, find three indices i < j < k where:
p[i] < p[j] (element at j is greater than element at i) p[k] < p[j] (element at j is greater than element at k)
If such a triplet exists, output "YES" followed by the three indices (1-indexed). Otherwise, output "NO".
Example:
text Input: [1, 2, 4, 3] Output: YES 1 2 3 Explanation: p[0]=1 < p[1]=2, and p[2]=4 > p[1]=2, but p[2]=4 > p[3]=3 Better: p[1]=2 > p[0]=1 and p[1]=2 < p[2]=4, wait that's wrong Actually: p[0]=1 < p[1]=2 and p[3]=3 < p[2]=4, so indices are 1,2,3
Intuition Behind Stack Approach
The key insight is that we're looking for a "peak pattern": an element that rises from a previous element and then falls to a next element. A stack naturally tracks this ascending-then-descending pattern.
Why Use a Stack?
Track potential starting points: The stack stores candidate elements that could be part of our triplet Maintain order: Stack preserves the sequential relationship between elements Easy backtracking: When we find a valid pattern, we can retrieve all indices from the stack
Detailed Algorithm Phase 1: Initialization
For each test case:
Read the array p of size x
Initialize flags:
flag1 = true: Looking for the middle (peak) element
flag2 = false: Haven't found a valid triplet yet
Create an empty stack to store (value, index) pairs
Create an empty vector ans to store result indicesPhase 2: Finding the Triplet
text For each starting position j from 0 to x-1: 1. Reset flag1 = true (crucial for each new attempt) 2. Push current element (p[j], j) onto stack as potential first element
3. Scan forward from position i = j+1 to x-1:
Case A: flag1 is true (looking for peak)
- Check if p[i] > stack.top()
- If YES:
* Push (p[i], i) onto stack (this is our peak candidate)
* Set flag1 = false (now look for descending element)
Case B: flag1 is false (have peak, looking for descending)
- Check if p[i] < stack.top()
- If YES:
* Add i to ans (third element index)
* Pop all from stack and add indices to ans
* Set flag2 = true (found valid triplet!)
* Break from inner loop
4. If flag2 is true, break from outer loop
5. Otherwise, clear stack and try next starting positionPhase 3: Output
Sort the ans vector to get indices in order If flag2 is true, print "YES" and the three indices (add 1 for 1-indexing) Otherwise, print "NO"
Step-by-Step Dry Run
Let's trace through p = [1, 2, 4, 3]: Attempt 1: j=0 (starting at index 0)
Initial state:
flag1 = true, flag2 = false Push (1, 0) → Stack: [(1, 0)]
Inner loop i=1:
flag1 = true, check: p[1]=2 > top=1? YES Push (2, 1) → Stack: [(1, 0), (2, 1)] Set flag1 = false
Inner loop i=2:
flag1 = false, check: p[2]=4 < top=2? NO (4 > 2) Continue
Inner loop i=3:
flag1 = false, check: p[3]=3 < top=2? NO (3 > 2) Continue
End of inner loop:
flag2 = false, so clear stack Try next j
Attempt 2: j=1 (starting at index 1)
Initial state:
flag1 = true (reset!), flag2 = false Push (2, 1) → Stack: [(2, 1)]
Inner loop i=2:
flag1 = true, check: p[2]=4 > top=2? YES Push (4, 2) → Stack: [(2, 1), (4, 2)] Set flag1 = false
Inner loop i=3:
flag1 = false, check: p[3]=3 < top=4? YES!
Add 3 to ans → ans = [3]
Pop stack and add indices:
Pop (4, 2) → ans = [3, 2]
Pop (2, 1) → ans = [3, 2, 1]
Set flag2 = true
Break!Output:
Sort ans: [1, 2, 3] Print: YES Print: 2 3 4 (adding 1 for 1-indexing)
Implementation Details Why Two Flags?
flag1: State machine control
true = searching for peak element
false = searching for descending element
Must reset for each outer loop iteration!
flag2: Solution found indicator
true = valid triplet found, can terminate
false = keep searchingTime Complexity: O(n²) — The nested loop structure causes worst-case quadratic behavior when no valid triplet exists. The outer loop iterates through n starting positions, and for each position, the inner loop scans the remaining elements (n-j iterations), resulting in 1+2+3+...+n = n(n+1)/2 = O(n²) operations. Best case is O(n) when the triplet is found in the first outer loop iteration with an early break. Space Complexity: O(n) — We use a stack that can theoretically grow to size n in worst case, though practically it holds at most 2 elements (the first element and the peak). The answer vector stores exactly 3 indices, contributing O(1) space, and the input array requires O(n) space, making the total auxiliary space O(n).
there can be many more optimizations in the code, like using a set instead of using a vector & sorting just for three elements but the main point is intuition, so i didn't look much into it, and although not an optimal solution(far from it), i thought sharing it would be better.
solution link https://codeforces.me/problemset/submission/1380/356095328
Dhanyavadamulu.




