Stock Span Problem Using Stack in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Stock Span Calculation

What is the output of the following code that calculates the stock span for the given prices?

DSA C

int prices[] = {100, 80, 60, 70, 60, 75, 85};
int n = 7;
int span[7];
int stack[7];
int top = -1;

for (int i = 0; i < n; i++) {
    while (top >= 0 && prices[stack[top]] <= prices[i]) {
        top--;
    }
    span[i] = (top < 0) ? (i + 1) : (i - stack[top]);
    stack[++top] = i;
}

for (int i = 0; i < n; i++) {
    printf("%d ", span[i]);
}

A [1, 1, 2, 2, 3, 3, 4]

B [1, 2, 3, 4, 5, 6, 7]

C [1, 1, 1, 2, 1, 4, 6]

D [1, 1, 1, 1, 1, 1, 1]

💡 Hint

Think about how the stack helps track previous higher prices to calculate spans.

The stack stores indices of days with higher prices. For each day, span is calculated as the difference between current day and last higher price day. If none, span is current day + 1.

🧠 Conceptual

intermediate

Understanding Stack Usage in Stock Span

Why do we use a stack to solve the Stock Span Problem efficiently?

A To sort the stock prices in ascending order before calculating spans.

B To keep track of indices of previous days with higher stock prices for quick span calculation.

C To store the spans directly as they are calculated for each day.

D To reverse the order of stock prices for backward traversal.

💡 Hint

Think about how the stack helps avoid repeated comparisons.

The stack holds indices of days with prices higher than the current day, allowing us to find the nearest higher price day quickly and calculate the span in O(n) time.

🔧 Debug

advanced

Identify the Bug in Stock Span Code

What error will the following code produce when calculating stock spans?

DSA C

int prices[] = {10, 4, 5, 90, 120, 80};
int n = 6;
int span[6];
int stack[6];
int top = 0;
stack[top] = 0;
span[0] = 1;

for (int i = 1; i < n; i++) {
    while (top >= 0 && prices[stack[top]] <= prices[i]) {
        top--;
    }
    span[i] = (top < 0) ? (i + 1) : (i - stack[top]);
    stack[++top] = i;
}

for (int i = 0; i < n; i++) {
    printf("%d ", span[i]);
}

A Compilation error due to uninitialized variables

B Runtime error due to stack underflow when top becomes -1 and then decremented again

C Outputs incorrect spans: 1 1 1 1 1 1

D Runs correctly and outputs: 1 1 2 4 5 1

💡 Hint

Check how the stack top is initialized and updated before the loop.

The code initializes top to 0 and sets stack[0] = 0 before the loop, so the stack is never empty inside the loop. The while loop correctly decrements top and checks for underflow. The code runs correctly and outputs the expected spans.

❓ Predict Output

advanced

Output of Stock Span with Repeated Prices

What is the output of the stock span calculation for the prices array with repeated values?

DSA C

int prices[] = {30, 35, 35, 40, 38, 38, 42};
int n = 7;
int span[7];
int stack[7];
int top = -1;

for (int i = 0; i < n; i++) {
    while (top >= 0 && prices[stack[top]] <= prices[i]) {
        top--;
    }
    span[i] = (top < 0) ? (i + 1) : (i - stack[top]);
    stack[++top] = i;
}

for (int i = 0; i < n; i++) {
    printf("%d ", span[i]);
}

A [1, 2, 3, 4, 1, 2, 7]

B [1, 1, 1, 1, 1, 1, 1]

C [1, 2, 2, 4, 1, 2, 7]

D [1, 2, 1, 4, 1, 1, 7]

💡 Hint

Remember that equal prices are included in the span calculation as less or equal.

The stack pops indices with prices less than or equal to current price, so repeated prices increase the span count. The output is [1, 2, 3, 4, 1, 2, 7].

🧠 Conceptual

expert

Time Complexity of Stock Span Algorithm Using Stack

What is the time complexity of the stock span problem solution using a stack and why?

A O(n) because each element is pushed and popped at most once from the stack.

B O(n^2) because for each element we may compare with all previous elements.

C O(log n) because the stack operations are logarithmic in size.

D O(1) because the span is calculated in constant time for each element.

💡 Hint

Consider how many times each element can be pushed or popped from the stack.

Each price index is pushed onto the stack once and popped at most once, so total operations are proportional to n, making the algorithm O(n).