Alternative Stack-Based Solution for 1380A — Three Indices

Revision en1, by musamiya, 2026-01-01 21:35:40

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 indices

Phase 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 position

Phase 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 searching

Time 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.

Tags *900, stack, data structure

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English musamiya 2026-01-01 21:35:40 5584 Initial revision (published)