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

Practice

1. What does the Stock Span Problem calculate for each day in a list of stock prices?

easy

A. The maximum stock price in the entire list

B. The number of consecutive days before the current day with a price less than or equal to the current day's price

C. The difference between the highest and lowest stock price

D. The total sum of stock prices up to the current day

Solution

1. Step 1: Understand the problem definition

   The Stock Span Problem finds how many consecutive previous days had stock prices less than or equal to the current day's price.

2. Step 2: Identify what is calculated for each day

   For each day, it counts the number of consecutive days before it with prices not greater than the current day's price.

3. Final Answer:

   The number of consecutive days with price less or equal to current day -> Option B

4. Quick Check:

   Span counts consecutive smaller/equal prices [OK]

Hint: Span counts consecutive days with price ≤ current day price [OK]

Common Mistakes:

• Confusing span with maximum price
• Calculating total sum instead of span
• Counting days with price greater than current

2. Which of the following C code snippets correctly initializes an empty stack for solving the Stock Span Problem?

easy

A. int stack[100]; int top = -1;

B. int stack[] = {0}; int top = 0;

C. int *stack; top = NULL;

D. stack = new int[100]; top = -1;

Solution

1. Step 1: Identify correct stack initialization in C

   In C, stack is usually an array with an integer top initialized to -1 to indicate empty stack.

2. Step 2: Check each option

   int stack[100]; int top = -1; correctly declares an int array and sets top to -1. int stack[] = {0}; int top = 0; initializes top to 0 which is incorrect for empty stack. int *stack; top = NULL; uses pointer and NULL incorrectly. stack = new int[100]; top = -1; uses 'new' which is C++ syntax, not C.

3. Final Answer:

   int stack[100]; int top = -1; -> Option A

4. Quick Check:

   Array + top = -1 initializes empty stack in C [OK]

Hint: Use array and top = -1 for empty stack in C [OK]

Common Mistakes:

• Using C++ 'new' keyword in C code
• Setting top to 0 instead of -1
• Using uninitialized pointers for stack

3. What is the output span array for the stock prices [100, 80, 60, 70, 60, 75, 85] using the Stock Span algorithm?

medium

A. [1, 1, 1, 2, 1, 4, 6]

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

C. [1, 1, 2, 2, 3, 3, 4]

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

Solution

1. Step 1: Calculate span for each day

   Day 0: price=100, no previous, span=1
   Day 1: price=80, previous 100 > 80, span=1
   Day 2: price=60, previous 80 > 60, span=1
   Day 3: price=70, previous 60 ≤ 70, span=1+1=2
   Day 4: price=60, previous 70 > 60, span=1
   Day 5: price=75, previous 60 ≤ 75, count 1 (day4), previous 70 ≤ 75, count 2 (day3), previous 60 ≤ 75, count 3 (day2), previous 80 > 75 stop, span=4
   Day 6: price=85, previous 75 ≤ 85, count 1 (day5), previous 60 ≤ 85, count 2 (day4), previous 70 ≤ 85, count 3 (day3), previous 60 ≤ 85, count 4 (day2), previous 80 ≤ 85, count 5 (day1), previous 100 > 85 stop, span=6

2. Step 2: Write final span array

   The span array is [1, 1, 1, 2, 1, 4, 6].

3. Final Answer:

   [1, 1, 1, 2, 1, 4, 6] -> Option A

4. Quick Check:

   Span counts consecutive smaller/equal prices [OK]

Hint: Count consecutive previous days with price ≤ current day [OK]

Common Mistakes:

• Counting all previous days instead of consecutive
• Ignoring equal prices in span
• Miscounting span for days with fluctuating prices

4. Identify the error in the following C code snippet for Stock Span calculation:

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

medium

A. The condition 'top != -1' should be 'top == -1'

B. The stack push operation should be before calculating span

C. No error; code correctly calculates the stock span

D. The comparison operator in while loop should be '<' instead of '<='

Solution

1. Step 1: Analyze the while loop condition

   The while loop pops indices from stack while the price at those indices is less than or equal to current price, which is correct for span calculation.

2. Step 2: Check span calculation and stack push

   Span is set to i+1 if stack empty, else difference between current index and top of stack index. Then current index is pushed. This matches the standard algorithm.

3. Final Answer:

   No error; code correctly calculates the stock span -> Option C

4. Quick Check:

   Standard stack-based span algorithm used [OK]

Hint: Check while condition and span formula carefully [OK]

Common Mistakes:

• Changing <= to < breaks span logic
• Pushing before span calculation causes wrong results
• Incorrect stack empty condition

5. Given stock prices [10, 4, 5, 90, 120, 80], how would the Stock Span algorithm change if we want to count days with strictly less price (not less or equal)? What is the resulting span array?

hard

A. [1, 1, 2, 4, 5, 2]

B. [1, 1, 1, 4, 5, 1]

C. [1, 1, 1, 3, 4, 1]

D. [1, 1, 2, 4, 5, 1]

Solution

1. Step 1: Understand change from ≤ to < in comparison

   Changing from less or equal to strictly less means while popping from stack, we pop only if previous price is strictly less than current price, not equal.

2. Step 2: Calculate span with strict less condition

   Day 0: 10, span=1
   Day 1: 4, previous 10 > 4, span=1
   Day 2: 5, previous 4 < 5, pop 4, span=2
   Day 3: 90, previous 5 < 90, pop 5; previous 10 < 90, pop 10; stack empty, span=4
   Day 4: 120, previous 90 < 120, pop 90; stack empty, span=5
   Day 5: 80, previous 120 > 80, span=1 (no pop)
   But since we pop only if strictly less, equal prices would not pop. Here no equal prices affect.

3. Final Answer:

   [1, 1, 2, 4, 5, 1] -> Option D

4. Quick Check:

   Strict less changes popping condition, span updated accordingly [OK]

Hint: Use '<' instead of '<=' in while condition for strict less [OK]

Common Mistakes:

• Not updating while condition correctly
• Miscounting span for last day
• Assuming equal prices pop stack