Stock span problem

Intuition:

The brute force to solve the problem is to start counting the days (for each day) where the stock prices were less than or equal to the price of stocks on current day.

Approach:

Initialise an array to store the answer. Start traversing on the given array.
For every element, traverse back till the stock prices are less than or equal to the stock prices on current day.
Store the stock span for each day. Once done, return the answer.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the span of stock prices for each day
    vector <int> stockSpan(vector<int> arr, int n) {
        
        // To store the answer
        vector<int> ans(n);
        
        // Traverse on the array
        for(int i=0; i < n; i++) {
            
            // To store the current span of stocks
            int currSpan = 0;
            
            // Traversing backwards to find stock span
            for(int j=i; j >= 0; j--) {
            
                // Update stock span
                if(arr[j] <= arr[i]) {
                    currSpan++;
                }
                
                // Else break out from loop
                else break;
            }
            
            // Store the current span
            ans[i] = currSpan;
        }
        
        // Return the result
        return ans;
    }
};

int main() {
    int n = 7;
    vector<int> arr = {120, 100, 60, 80, 90, 110, 115};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the span 
    of stock prices for each day */
    vector<int> ans = sol.stockSpan(arr, n);
    
    cout << "The span of stock prices is: ";
    for(int i=0; i < n; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find the span of stock prices for each day
    public int[] stockSpan(int[] arr, int n) {
        
        // To store the answer
        int[] ans = new int[n];
        
        // Traverse on the array
        for(int i = 0; i < n; i++) {
            
            // To store the current span of stocks
            int currSpan = 0;
            
            // Traversing backwards to find stock span
            for(int j = i; j >= 0; j--) {
            
                // Update stock span
                if(arr[j] <= arr[i]) {
                    currSpan++;
                }
                
                // Else break out from loop
                else break;
            }
            
            // Store the current span
            ans[i] = currSpan;
        }
        
        // Return the result
        return ans;
    }
    
    public static void main(String[] args) {
        int n = 7;
        int[] arr = {120, 100, 60, 80, 90, 110, 115};
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to find the span 
        of stock prices for each day */
        int[] ans = sol.stockSpan(arr, n);
        
        System.out.print("The span of stock prices is: ");
        for(int i = 0; i < n; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}
class Solution:
    # Function to find the span of stock 
    # prices for each day
    def stockSpan(self, arr, n):
        
        # To store the answer
        ans = [0] * n
        
        # Traverse on the array
        for i in range(n):
            
            # To store the current span of stocks
            currSpan = 0
            
            # Traversing backwards to find stock span
            for j in range(i, -1, -1):
            
                # Update stock span
                if arr[j] <= arr[i]:
                    currSpan += 1
                
                # Else break out from loop
                else:
                    break
            
            # Store the current span
            ans[i] = currSpan
        
        # Return the result
        return ans

# Main code
if __name__ == "__main__":
    n = 7
    arr = [120, 100, 60, 80, 90, 110, 115]
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to find the span 
    # of stock prices for each day
    ans = sol.stockSpan(arr, n)
    
    print("The span of stock prices is:", end=" ")
    for span in ans:
        print(span, end=" ")
class Solution {
    // Function to find the span of stock prices for each day
    stockSpan(arr, n) {
        
        // To store the answer
        let ans = new Array(n);
        
        // Traverse on the array
        for (let i = 0; i < n; i++) {
            
            // To store the current span of stocks
            let currSpan = 0;
            
            // Traversing backwards to find stock span
            for (let j = i; j >= 0; j--) {
            
                // Update stock span
                if (arr[j] <= arr[i]) {
                    currSpan++;
                }
                
                // Else break out from loop
                else break;
            }
            
            // Store the current span
            ans[i] = currSpan;
        }
        
        // Return the result
        return ans;
    }
}

// Main code
const n = 7;
const arr = [120, 100, 60, 80, 90, 110, 115];

/* Creating an instance of 
Solution class */
const sol = new Solution(); 

/* Function call to find the span 
of stock prices for each day */
const ans = sol.stockSpan(arr, n);

console.log("The span of stock prices is:", ans.join(" "));

Complexity Analysis:

Time Complexity: O(N²) (where N is the length of given array)
Using two nested loops.

Space Complexity: O(1)
Using only a couple of variables.

Pre Requisite: Next Greater Element

Intuition:

As stated in the problem, the stock span is the number of consecutive days for which the stock price was less than or equal to the price on current day. Hence, to get the stock span for current day, the aim is to find the position of its previous greater element. This will significantly improve the solution by eliminating multiple backwards traversals on the given array.

Understanding:

Finding the previous greater element is similar to finding the next greater element, the only difference is that the direction of traversal will be reversed while maintaining the decreasing order of elements in the stack (monotonic stack).

Approach:

Determine the indices of previous greater elements using monotonic stack (maintaining elements in decreasing order in a stack)
Once the indices are known, the stock span for each day will be difference between the current index and the index of its previous greater element.
Traverse the array, updating the stock span for each day.
After the traversal is over, return the result.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to find the indices of previous 
    greater element for each element in the array */
    vector<int> findPGE(vector<int> arr) {
        
        int n = arr.size(); //size of array
        
        // To store the previous greater elements
        vector<int> ans(n);
        
        // Stack to get elements in LIFO fashion
        stack<int> st;
        
        // Start traversing from the front
        for(int i=0; i < n; i++) {
            
            // Get the current element
            int currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the greater element */
            while(!st.empty() && arr[st.top()] <= currEle) {
                st.pop();
            }
            
            /* If the greater element is not 
            found, stack will be empty */
            if(st.empty()) 
                ans[i] = -1;
                
            // Else store the answer
            else 
                ans[i] = st.top();
            
            // Push the current index in the stack 
            st.push(i);
        }
        
        // Return the result
        return ans;
    }
    
public:
    // Function to find the span of stock prices for each day
    vector <int> stockSpan(vector<int> arr, int n) {
        
        // Get the indices of previous greater elements
        vector<int> PGE = findPGE(arr);
        
        
        // To store the answer
        vector<int> ans(n);
        
        // Compute the result
        for(int i=0; i < n; i++) {
            ans[i] = i - PGE[i];
        }
        
        // Return the result
        return ans;
    }
};

int main() {
    int n = 7;
    vector<int> arr = {120, 100, 60, 80, 90, 110, 115};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the span 
    of stock prices for each day */
    vector<int> ans = sol.stockSpan(arr, n);
    
    cout << "The span of stock prices is: ";
    for(int i=0; i < n; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    /* Function to find the indices of previous 
    greater element for each element in the array */
    private int[] findPGE(int[] arr) {
        
        int n = arr.length; //size of array
        
        // To store the previous greater elements
        int[] ans = new int[n];
        
        // Stack to get elements in LIFO fashion
        Stack<Integer> st = new Stack<>();
        
        // Start traversing from the front
        for(int i = 0; i < n; i++) {
            
            // Get the current element
            int currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the greater element */
            while(!st.isEmpty() && arr[st.peek()] <= currEle) {
                st.pop();
            }
            
            /* If the greater element is not 
            found, stack will be empty */
            if(st.isEmpty()) 
                ans[i] = -1;
                
            // Else store the answer
            else 
                ans[i] = st.peek();
            
            // Push the current index in the stack 
            st.push(i);
        }
        
        // Return the result
        return ans;
    }
    
    // Function to find the span of stock prices for each day
    public int[] stockSpan(int[] arr, int n) {
        
        // Get the indices of previous greater elements
        int[] PGE = findPGE(arr);
        
        // To store the answer
        int[] ans = new int[n];
        
        // Compute the result
        for(int i = 0; i < n; i++) {
            ans[i] = i - PGE[i];
        }
        
        // Return the result
        return ans;
    }
    
    public static void main(String[] args) {
        int n = 7;
        int[] arr = {120, 100, 60, 80, 90, 110, 115};
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to find the span 
        of stock prices for each day */
        int[] ans = sol.stockSpan(arr, n);
        
        System.out.print("The span of stock prices is: ");
        for(int i = 0; i < n; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}
class Solution:
    # Function to find the indices of previous 
    # greater element for each element in the array
    def findPGE(self, arr):
        
        n = len(arr) # size of array
        
        # To store the previous greater elements
        ans = [0] * n
        
        # Stack to get elements in LIFO fashion
        st = []
        
        # Start traversing from the front
        for i in range(n):
            
            # Get the current element
            currEle = arr[i]
            
            # Pop the elements in the stack until 
            # the stack is not empty and the top 
            # element is not the greater element
            while st and arr[st[-1]] <= currEle:
                st.pop()
            
            # If the greater element is not 
            # found, stack will be empty
            if not st:
                ans[i] = -1
                
            # Else store the answer
            else:
                ans[i] = st[-1]
            
            # Push the current index in the stack 
            st.append(i)
        
        # Return the result
        return ans
    
    # Function to find the span of stock prices for each day
    def stockSpan(self, arr, n):
        
        # Get the indices of previous greater elements
        PGE = self.findPGE(arr)
        
        # To store the answer
        ans = [0] * n
        
        # Compute the result
        for i in range(n):
            ans[i] = i - PGE[i]
        
        # Return the result
        return ans

# Main code
if __name__ == "__main__":
    n = 7
    arr = [120, 100, 60, 80, 90, 110, 115]
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to find the span of stock prices for each day
    ans = sol.stockSpan(arr, n)
    
    print("The span of stock prices is:", end=" ")
    for span in ans:
        print(span, end=" ")
class Solution {
    /* Function to find the indices of previous 
    greater element for each element in the array */
    findPGE(arr) {
        
        const n = arr.length; // size of array
        
        // To store the previous greater elements
        const ans = new Array(n).fill(0);
        
        // Stack to get elements in LIFO fashion
        const st = [];
        
        // Start traversing from the front
        for (let i = 0; i < n; i++) {
            
            // Get the current element
            const currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the greater element */
            while (st.length && arr[st[st.length - 1]] <= currEle) {
                st.pop();
            }
            
            /* If the greater element is not 
            found, stack will be empty */
            if (st.length === 0) 
                ans[i] = -1;
                
            // Else store the answer
            else 
                ans[i] = st[st.length - 1];
            
            // Push the current index in the stack 
            st.push(i);
        }
        
        // Return the result
        return ans;
    }
    
    // Function to find the span of stock prices for each day
    stockSpan(arr, n) {
        
        // Get the indices of previous greater elements
        const PGE = this.findPGE(arr);
        
        // To store the answer
        const ans = new Array(n).fill(0);
        
        // Compute the result
        for (let i = 0; i < n; i++) {
            ans[i] = i - PGE[i];
        }
        
        // Return the result
        return ans;
    }
}

// Main code
const n = 7;
const arr = [120, 100, 60, 80, 90, 110, 115];

/* Creating an instance of 
Solution class */
const sol = new Solution(); 

/* Function call to find the span 
of stock prices for each day */
const ans = sol.stockSpan(arr, n);

console.log("The span of stock prices is:", ans.join(" "));

Complexity Analysis:

Time Complexity: O(N)

Finding the indices of previous greater elements takes O(N) time.
Traversing the array once to find the stock span taking O(N) time.

Space Complexity: O(N)
The stack space used to find the previous greater elements can go up to O(N) in the worst case.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Understanding:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code