29 Jun 2019

Next Greater Element

Problem Statement:
      Print the next greater element to every element in an array , if no greater element exists for a number
 print -1.

Given Array :   7     22    4      12     25      3      9
Output:            22   25    12    25     -1      9      -1

Solution:

The above problem can be solved using stack.

Below is the sub-routine implementation:
Please comment and post suggestions
Happy Coding !! :)

28 Jun 2019

Odd one out.

Problem Statment : Find the element which occurs once where as other numbers appears N Times in an array

For example here [5, 5, 4, 8, 4, 5, 8, 9, 4, 8] all the number appear 3 times except 9 which appears 1 time.

Solution : 

This problem can be solved using bit operation in a very efficient way

Time Complexity : O(n)
Space : O(1)

Code Below :


Please post your comments and suggestions.
Happy Coding !! :)



22 Jun 2019

Rain Water Trap

Problem Statement : 
Given n non-negative integers representing building heights where the width

of each bar is 1, compute how much water it is able to trap after raining.

Below is the figure depicting the buildings and the gap between the building would trap the water.

Buildings with gaps to trap rain water.


Solution : 
   In this problem, we would calculate left max and right Max for a given bar and subtract the height of the bar from the minimum of L_max and R_max and add the result of each bar to obtain the final answer.

<math xmlns="http://www.w3.org/1998/Math/MathML"><munderover><mrow><mo>&#x2211;</mo><mo>&#xA0;</mo></mrow><mrow/><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></munderover></math>min(LH[i] - RH[i]) - H[i])

where LH[i] means Left Height Max ,
           RH[i] means Right Height Max and 
           H[i] means Height of building 'i'.

This is a simple gist of the problem, we will discuss the various approach to solve this problem.

Approach 1 :
  The Brute Force, this is the father of all solutions and every developer is the master of it, this is always the first answer but never accepted by the interviewer, anyways we still discuss this to optimize our solution further.

In this approach, we will traverse the elements and every element will have two pointers `left` and `right`,  left pointer will move towards left until a bigger number is found for i-th element and the right pointer will move towards right until the bigger element is found for the i-th element.

so water stored at i-th element = Min(L_max , R_max) - height[i].

I hope you will be able to code for this,  if not you can find the code here.

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2 : 
   The Dynamic Programming(DP) approach, in this approach we will use two most important properties of DP, a. Overlapping subproblem and Optimal Substructure.

On every bar, the water collected is calculated by itself as well as a portion of it is also calculated by other bars, this is a depiction of Overlapping subproblem.

Optimal Substructure, we can represent the calculation of water on a bar that is subproblem and it is contributed by other bars as well this can be represented by the below equation.

<math xmlns="http://www.w3.org/1998/Math/MathML"><munderover><mrow><mo>&#x2211;</mo><mo>&#xA0;</mo></mrow><mrow/><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></munderover></math>min(LH[i] - RH[i]) - H[i])

So here we will take two arrays left[] and right[] which will store the left_max and right_max for every bar respectively at the corresponding index of the bar. Thereafter we calculate the water level stored on each bar by Min(Lmax - Rmax) - bar_height. Summation of the previous value would give us the trapped water.

Code below:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
     //Dynamic Programming Apporach to Trap rain water problem solution
     static int trapWaterUsingDP(int[] bars) {
     if(bars == null || bars.length < 3) 
      return 0;
     
     int len = bars.length, trappedWater = 0;
     int[] left = new int[len];
     int[] right = new int[len];
     
     //NB. for left most bar lmax would be 0, so counter is stated with 1,
     for(int i=1;i<len;i++) 
      left[i] = Math.max(left[i-1], bars[i-1]);
     
     // similarly for right most bar rmax would be 0 at len-1. 
     for(int i= len -2 ;i >= 0;i--) 
      right[i] = Math.max(right[i+1], bars[i+1]);
     
     
     for(int i=0;i<len;i++)
      trappedWater += Math.max(0, Math.min(left[i], right[i]) - bars[i]);
     
     return trappedWater;
    }

Time Complexity : O(n)
Space Complexity : O(n) , since we have used n + n which is 2n, removings constants gives us O(n) complexity

Approach 3:
   The Stack-based approach, we will now solve the above problem with the stack-based approach, in the last approach, we improved on Time Complexity but deteriorated Space complexity compared to approach 1.

This approach will give us both improved Time and Space complexity.
Algorithm below :
1. Iterate over each tower
     a. while stack is not empy and stack.peek() > current
         i. top = stack.pop()
         ii. dist = current - stack.peek() -1
         iii height = min(current, stack.peek()) - height[top]
         iv. water  += dist * height
  b. push
  c. next tower

Code below.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
     //Stack based Approach to Trap rain water problem solution
     static int trapWaterUsingStack(int[] bars) {
      if(bars == null || bars.length < 3) 
       return 0;
      
      Stack<Integer> stack = new Stack<>();
      stack.push(0);
      
      int len = bars.length, waterTrapped = 0;
      for(int i=1; i < len ; i++)
      {
       while(!stack.isEmpty() && bars[stack.peek()] < bars[i]) {
        int top = stack.pop();
        if(!stack.isEmpty()) {
         int dist = stack.isEmpty() ?  0 : i - stack.peek() - 1 ;
         int effectiveHeight = Math.min(bars[i], bars[stack.peek()]) - bars[top];
            waterTrapped += dist * effectiveHeight;
        }
       }
       stack.push(i);
      }
      return waterTrapped;
     }

Time Complexity: O(n)
Space Complexity: O(n)

Approach 4: 
     Two Pointer Approach : 

In this approach,  we will use two-pointers and switch between left and right pointer for the movement.
Extreme bars will not store any water.
We will continue to move from left until left is smaller than right, as soon as right becomes smaller than left we will start move from right.



For complete code use this link (Code)
Please post your suggestions and comments.
Happy Coding !!

20 Jun 2019

Stock Span Problem

Problem Statment : 
       We are given list price of a stock for N days,  find the stock span of each day. Stock spam is defined as the consecutive number of days where the stock price was less or equal to the given day stock price.

For ex. for   P  = {11, 9, 7, 5, 4, 6, 8, 10, 7, 9}  the span is S = {1, 1, 1, 1, 1, 3, 4, 7, 1, 2}




Solution :


I hope the solution looks evident by looking at the graph, so we plot the span values of each stock price below to make it much more meaningful and clear. 



We will be discussing multiple approaches to solve the problem. 

Approach 1 : 
We will first consider the naive solution which will have a time complexity of O(n^2). 

Here for each item traverse on the left of the array until you find the element bigger than the current one. For every move towards the left increment the counter of the current element by 1.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
  int[] solve1(int[] stocks) {
 int len = stocks.length, i , j ;
 int[] span = new int[len];
 span[0] = 1;
  
 for (i = 1; i < len; i++) { 
  for (j = i - 1, span[i] = 1; j >= 0 && stocks[i] >= stocks[j]; j--, span[i]++);
 }
 return span;
  }

Time Complexity: O(n^2)
Space Complexity: O(n)

We surely can do better than this, moving to the next approach


Approach 2 :

In this approach, we will consider a stack-based solution to improve Time complexity.
Here the idea is if the next element is smaller then the stock span of that element is 1 (eg,  70, 65) otherwise if the next element is greater than the top element (eg, 70, 65, 80) then there is possibility that incoming element is greater than further elements in the stack so keep popping until you find a greater element index than the current element and calculate the span using span[i] = i - price[stack.peek()]  or otherwise if the stack is empty span[i] = i+1.

Let us write the code for this. (i am writing a code in order to understand the logic, you improvise it to make it shortened).


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
  int[] solve(int[] stocks)
    {
 Stack<Integer> stack = new Stack<Integer>();
 stack.push(0);
 int[] sol = new int[stocks.length];
 sol[0]=1;
  
 for(int i=1;i<stocks.length;i++)
 {
     //if incoming element is small, Pop until u find greater element index in the stack 
     for(;!stack.isEmpty() && stocks[stack.peek()] < stocks[i]; stack.pop());
  
     sol[i] = stack.isEmpty() ? i + 1: i - stack.peek();
     stack.push(i);
 }
 System.out.println(Arrays.toString(sol));
 return sol;
    }

In spite of the fact that there are nested loops in the above code, the time complexity is O(n) because we are traversing all the elements just once. In the worst case, we may have to put all the elements into the stack and then pop out all the elements (eg. 80,70, 60, 50, 40, 90) so the complexity would be O(2*n) which is of the order of O(n).

Time Complexity: O(n)
Space Complexity: O(n)

Executable Code below:

Please post your comments and suggestions.
Happy Coding !! :)

19 Jun 2019

Largest Area in a Histogram

Problem Statement : 
      Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.




In the above histogram width of each bar is 1 and heights are H = [2, 1, 5, 6, 2, 3]. 


Solution: 

By brute force algorithm, we can consider each bar every time and consider all other bars adjacent to it which are equal or greater and find the area by Height of the bar multiplied by right and left index difference plus one

Area = Bar Height * (right_index - left_index + 1)

The time complexity for this case would be (n^2) i.e. n-squared. 

We would be discussing another optimised technique which will have a complexity of O(n) using stack. 


We would essentially use same trick as we had done in the Brute force but with storage in a stack we will find a better optimised solution, The trick is to compute left and right index of the of bar such that all bars between these indices are either equal or greater than the bar in consideration. 

Traverse all the bars from left to right and push the bar to the stack if the stack is empty or if the bar is greater than the top of the stack. Once the next incoming bar is smaller than the top of the stack, anchor the index here and this would act as right_index start. Pop the bar and calculate the area as the smallest bar for this left index would be the updated top in the stack. 
i.e. A = bar_height * (right_index - 1 -  new_top_index). 

If this is slightly confusing then lets write the algorithm for it. 

Algorithm :
1. Create a empty stack. 
2. Push i , if stack is empty or H[i] is greater than stack.peek()
3. If the bar is small set anchor to i, continue to pop the indces from the stack until H[stack.peek()] is smaller H[i], for each element poped calculate the area evert time you pop element using 

A = bar_height(of the poped index) * (i - 1 - stack.peek()) 

when stack is empty, 
A = bar_height(of the poped index) * i

update Area A if the newly computed Area is greater than previous. 

4. If all the items are over and stack is still not empty repeat process 3.

Code below :



Let me know if you have any questions in the comments section or any feedback.
Happy Coding !! :)