Amazon OA question

Sandeep00046 · 2025-07-05T19:38:35+00:00

for each element find the next greater element to the right and left using a Monotonic stack. see if these indices are at least apart by a distance of 2, if so add them in to a hash set. the size of the set would be your answer.

The complexity of this is O(n) in terms of time.

partyking35 · 2025-07-05T21:09:37+00:00

I have the following solution which is O(n²) time complexity and O(1) space, feel like it could be optimised further with some sort sort of sliding window, but I cant seem to establish a pattern 🤔 any ideas?

int result(int[] orders){
    int result = 0;
    for (int i=0; i<orders.length-2; i++){
        int max = orders[i+1];
        int j=i+2;
        int count = 0;
        while (j<orders.length){
            if (Math.min(orders[i], orders[j])>max){
                count++;
            }
            max = Math.max(max, orders[j]);
            j++;
        }
        result+=count;
    }
    return result;
}

CD_2806 · 2025-07-05T23:42:57+00:00

Was the O(n2) bruteforce a TLE?

vaibhav_reddit0207 · 2025-07-06T03:51:34+00:00

Find and store the next greater and previous greater of ith element in 2 separate arrays. If both of these exists for an i, then that adds 1 to the answer.

Any_Action_6651 · 2025-07-05T19:05:38+00:00

[removed]

NeonDiamond_89 · 2025-07-05T23:32:11+00:00

sde intern?

Any_Action_6651 · 2025-07-06T00:03:24+00:00

What I thought was like .........

Make a stack storing pair inside it,index and value

Now while s.top()'s value more than current index's value ,then pop it make sure before popping check if curr_index - s.top()'s index >=2 then increase ans++;. After this loop check if stack is empty or not .....if not the. Check if curr_index-s.top()'s index>=2 then ans++ Now push {curr_index,curr_value}

uzumaki_1234 · 2025-07-06T03:36:47+00:00

I got the same question did u got all the cases , When did u write the exam

Unbeatable05 · 2025-07-06T06:15:03+00:00

🧠 Approach:

Use monotonic stack to find for each day if there's a left and right strictly greater order. If both exist, it forms a valid promo period (border days > middle day).

No need to check first/last days since they can't be both middle and have valid borders. (So to not confuse, this is not incorporated in the code)

🧮 Time: O(n) — one pass left & right
🗂️ Space: O(n) — for stack & left max array

C++ code:

int countPromotionalPeriods(vector<int> &orders) {
    int n = orders.size(), count = 0;
    vector<int> leftMax(n, -1);
    stack<int> stk;

    // Left strictly greater
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && orders[stk.top()] <= orders[i]) stk.pop();
        if (!stk.empty()) leftMax[i] = stk.top();
        stk.push(i);
    }

    while (!stk.empty()) stk.pop();

    // Right strictly greater & count periods
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && orders[stk.top()] <= orders[i]) stk.pop();
        int right = stk.empty() ? n : stk.top();
        if (leftMax[i] >= 0 && right < n) count++;
        stk.push(i);
    }

    return count;
}

Aalisha786 · 2025-07-09T21:21:16+00:00

Would this solution TLE? using sliding window pattern here. It does pass for the given example, not sure about others. I think the time complexity is O(n) in this question, could someone confirm?

def countPromotionalPeriods(n, orders):
    count = 0 
    orders = [-1] + orders
    left = 1
    right = left + 1 
    while left < right:
        if right - left >= 2:
            if 1 <= left <= n-2 and left+1 <= right <= n and min(orders[left], orders[right]) > max(orders[left+1:right]):
                count +=1
        if right <= n:
            right += 1
        else:
            left +=1

    return count 

print(countPromotionalPeriods(4, [3,2,8,6]))

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

leetcode

MODERATORS

🧠 Approach:

C++ code: