Immediate Previous Larger Number

Find the nearest previous number that is larger than each number in a sequence.

Understand the Problem

Problem Statement

Given N numbers, for each number in the sequence, print the nearest previous number that is larger than the current number. If no such number exists, print 0 for that position.

Example: For the sequence [455, 346, 76, 304], the immediate previous larger numbers are [0, 455, 346, 346] because:

455 has no previous number, so 0
346's previous larger is 455
76's previous larger is 346
304's previous larger is 346

Constraints

2 ≤ N ≤ 100000
Each number in the sequence can be any integer
Time complexity must be efficient for large N

Examples

Example 1

Input

11
455 346 76 304 488 374 385 433 350 9 1000

Output

0 455 346 346 0 488 488 488 433 350 0

Explanation

For each number: 455 has no previous (0), 346's previous larger is 455, 76's previous larger is 346, 304's previous larger is 346, 488 has no previous larger (0), 374's previous larger is 488, 385's previous larger is 488, 433's previous larger is 488, 350's previous larger is 433, 9's previous larger is 350, 1000 has no previous larger (0).

Example 2

Input

5
5 4 3 2 1

Output

0 5 4 3 2

Explanation

Each number is smaller than the previous one, so each number's immediate previous larger is simply the number that comes immediately before it.

Example 3

Input

5
1 2 3 4 5

Output

0 0 0 0 0

Explanation

Since the sequence is strictly increasing, no number has a previous number that is larger, so all outputs are 0.

Solution

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100000

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[MAX_N];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Stack to store indices of elements in decreasing order
    int stack[MAX_N];
    int top = -1;
    int result[MAX_N];
    
    for (int i = 0; i < n; i++) {
        // Remove elements from stack that are smaller than current
        while (top >= 0 && arr[stack[top]] <= arr[i]) {
            top--;
        }
        
        // If stack is empty, no previous larger element
        if (top == -1) {
            result[i] = 0;
        } else {
            result[i] = arr[stack[top]];
        }
        
        // Push current index to stack
        stack[++top] = i;
    }
    
    // Print results
    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    
    return 0;
}

Time:O(N) - Each element is pushed and popped from the stack at most once

Space:O(N) - Stack can store up to N elements in the worst case

Approach:

The C solution uses a stack-based approach to efficiently find the immediate previous larger number for each element.

Input Reading: Read N and the array of numbers
Stack Initialization: Use an array as a stack to store indices of elements in decreasing order
Processing Loop: For each element, pop elements from stack that are smaller than or equal to current element
Result Assignment: If stack is empty, assign 0 (no previous larger). Otherwise, assign the value at the top of stack
Stack Update: Push current index onto stack for future comparisons
Output: Print all results

This approach ensures O(N) time complexity since each element is pushed and popped from the stack at most once.

Visual Explanation

Loading diagram...

All Problems