Session 26: Stack and Queue 2

Original Session

Date: 04 Jan 2025

Topic: Stack & Queue

Concept: Next Greatest Element

Programs

1. 42. Trapping Rain Water
   1. leetcode here

   
   // With Sapce O(n)
   public int trap(int[] height) {
           
           int[] maxL = new int[height.length];
           int[] maxR = new int[height.length];
   
           maxL[0] = height[0];
           maxR[height.length - 1] = height[height.length - 1];
           for (int i = 1; i < height.length; i++){
   
               if (height[i] > maxL[i-1]) {
                   maxL[i] = height[i];
               } else {
                   maxL[i] = maxL[i-1];
               }
   
               if (height[height.length - 1 - i] > maxR[height.length - i]) {
                   maxR[height.length - 1 - i] = height[height.length - 1 - i];
               } else {
                   maxR[height.length - 1 - i] = maxR[height.length - i];
               }
           }
   
           int ans = 0;
           for (int i=0; i< height.length; i++) {
   
               int min = maxL[i] < maxR[i] ? maxL[i]: maxR[i];
               int result = min - height[i];
               if (result > 0) {
                   ans+=result;
               }
           }
   
           return ans;
       }
   
   // ---------------------------------------
   // With Space O(1)
   public int trap(int[] height) {
           
           if (height == null || height.length <= 0) {
               return 0;
           }
   
           int l=0, r=height.length-1, leftMax = height[l], rightMax = height[r];
           int res = 0;
   
           while (l<r) {
   
               if (leftMax < rightMax) {
                   l++;
                   leftMax = Math.max(leftMax, height[l]);
                   res += leftMax - height[l];
               } else {
                   r--;
                   rightMax = Math.max(rightMax, height[r]);
                   res += rightMax - height[r];
               }
           }
   
           return res;
       }

2. Next Greater To Right Video 58

   

   1. GFG here

   public ArrayList<Integer> nextLargerElement(int[] arr) {
           // code here
           
           int[] ans = new int[arr.length];
           Stack<Integer> stack = new Stack();
           
           for (int i = arr.length-1; i>=0; i--) {
               
               if (stack.isEmpty()) {
                   
                   ans[i] = -1;
                   stack.add(arr[i]);
               } else if (!stack.isEmpty() && stack.peek() > arr[i]) {
                   
                   ans[i] = stack.peek();
                   stack.add(arr[i]);
               } else {
                   i++;
                   stack.pop();
               }
               
           }
           
           ArrayList<Integer> arrayList = new ArrayList<>();
           for (int i : ans) {
               arrayList.add(i);
           }
           return arrayList;
       }

3. 121. Best Time to Buy and Sell Stock Video 1:24
   1. leetcode here

   public int maxProfit(int[] prices) {
           
       
           int maxProfit = 0;
           int minPrice = prices[0];
   
           for(int price: prices) {
   
               int profit = price - minPrice;
   
               maxProfit = Math.max(profit, maxProfit);
               minPrice = Math.min(price, minPrice);
           }
   
           return maxProfit;
       }

4. 122. Best Time to Buy and Sell Stock II
   1. leetcode here

   public int maxProfit(int[] prices) {
           
           int ans = 0;
           int buyPrice = prices[0];
   
           for(int price: prices) {
   
               int profit = price - buyPrice;
               if (profit > 0) {
                   ans += profit;
               }
               buyPrice = price;
           }
   
           return ans;
       }

5. 739. Daily Temperatures
   1. leetcode here

   public int[] dailyTemperatures(int[] temperatures) {
           
           int[] ans = new int[temperatures.length];
           Stack<Integer> stack = new Stack();
           Stack<Integer> temp = new Stack();
           int count = 1;
   
           for (int i = temperatures.length-1; i>=0; i--) {
               
               if (stack.isEmpty()) {
                   
                   ans[i] = 0;
                   temp.stream().forEach(stack::add);
                   stack.add(temperatures[i]);
                   temp.clear();
                   count = 1;
               } else if (!stack.isEmpty() && stack.peek() > temperatures[i]) {
                   
                   ans[i] = count;
                   temp.stream().forEach(stack::add);
                   stack.add(temperatures[i]);
                   temp.clear();
                   count = 1;
               } else {
                   i++;
                   count++;
                   temp.add(stack.pop());
               }
               
           }
           
           return ans;
       }
       
       /// Alternative approach ------------------
       
       public int[] dailyTemperatures(int[] temperatures) {
           
           int[] res = new int[temperatures.length];  // Result array
           Stack<int[]> stack = new Stack<>();        // Stack to store [temperature, index]
   
           for (int i = 0; i < temperatures.length; i++) {
               int currentTemp = temperatures[i];
               
               // While the stack is not empty and the current temperature is greater than the top of the stack
               while (!stack.isEmpty() && currentTemp > stack.peek()[0]) {
                   int[] stackElement = stack.pop();  // Pop the top element from the stack
                   int stackTemp = stackElement[0];
                   int stackIndex = stackElement[1];
                   res[stackIndex] = i - stackIndex;  // Calculate the difference in days
               }
               
               // Push the current temperature and index onto the stack
               stack.push(new int[] { currentTemp, i });
           }
   
           return res;
           
       }

6. 224. Basic Calculator
   1. leetcode here

   public int calculate(String s) {
           
           Stack<Integer> stack = new Stack();
           int ans = 0, sign = 1;
   
           for (int i=0; i<s.length(); i++) {
   
               char ch = s.charAt(i);
               if (Character.isDigit(ch)) {
   
                   int num = 0;
                   while (i < s.length() && 
                   Character.isDigit(s.charAt(i))) {
                       num = num*10 + (s.charAt(i) - '0');
                       i++;
                   }
                   i--;
                   ans += sign * num;
               } else if (ch == '+') {
                   sign = 1;
               } else if (ch == '-') {
                   sign = -1;
               } else if (ch == '(') {
                   stack.push(ans);
                   stack.push(sign);
                   ans = 0;
                   sign = 1;
               } else if (ch == ')') {
                   ans = stack.pop() * ans + stack.pop();
               }
           }
   
           return ans;
       }