Meeting Rooms

Given an array of intervals representing N meetings, find out if a person can attend all the meetings.

Input:
[[6,7],[2,4],[8,12]]
Output:
true
Explanation:
None of the meetings overlap with each other.

Input:
[[1,4],[2,5],[7,9]]
Output:
false
Explanation:
Meetings [1,4] and [2,5] overlap with each other.
This problem is commonly asked nowadays in Amazon, Facebook and Microsoft interview.


Thought Process

A person can not attend two or more meetings at one time. It means if the timings of two meetings are overlapping, then she/he will not able to attend it.
Now, the question comes in your mind that How to recognize/check that the two meetings are overlapping or not. We will use the time interval to check that the meetings are overlapping or not.

Follow below picture to get to know about overlapping.

Meeting Rooms
These are are the 4 Overlapping Situations.

Now, we have to check if one meeting interval is overlapping with other, then it is impossible to attend that meeting.

Brute Force

The Simple Solution is to compare every two meetings using the nested for loop and to check whether the intervals are overlapping or not. Two meetings overlap if one meeting is going on and other meeting starts before finishing the first meeting.

class Solution {
public:
    bool check_overlap(vector<int>first, vector<int>second)
    {
        if((first[0]>=second[0] && first[0]<second[1]) 
           || (second[0]>=first[0] && second[0] <first[1])){
            return true;
        }
        return false;
    }
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        int i,j;
        
        for(i=0;i<intervals.size();i++)
        {
            for(j=i+1;j<intervals.size();j++)
            {
                if(check_overlap(intervals[i],intervals[j]))
                {
                    return false;
                }
            }
        }
        return true;
    }
};

Time Complexity of the brute force implementation is O(n2), due to nested for loop where as space complexity is O(1)

Using Merge Intervals Technique

In this, what we do is we merge all the overlapping intervals. After Merging, we compare the number of intervals before merging and after merging. If the number of intervals is the same, then there are no conflicts in the meetings, it will run smoothly(no overlapping situation). If the total number of intervals are less after merging, then it means there were some overlapping intervals, so there will be conflicts in meetings.

If you wan to learn merging intervals in detail, go here.

First, Sort the intervals in ascending order.
  1. Initiate a 2-D vector array.
  2. Add the first interval into it.
  3. for every other intervals
    • check if the last interval in the vector array is overlapping with current interval, then pop the last interval from vector array and merge the both intervals and push it in the vector array.
    • check if the last interval in he vector array is not overlapping with current interval, push current interval in the vector array.
  4. if(size of vector array formed < size of initial intervals array given)
    • return false
    • else return true;
class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        int i,j;
        
        vector<vector<int>>v;
        if(intervals.size()==0)
        {
            return true;
        }
        sort(intervals.begin(), intervals.end());
        vector<int>l;
        l.push_back(intervals[0][0]);
        l.push_back(intervals[0][1]);
        v.push_back(l);
        
        for(i=1;i<intervals.size();i++)
        {
            vector<int> prev=v.back();
            //time to merge
            if(intervals[i][0]<prev[1])
            {
                l.clear();
                v.pop_back();
                l.push_back(prev[0]);
                l.push_back(max(prev[1],intervals[i][1]));
                v.push_back(l);
            }
            else
            {
                v.push_back(intervals[i]);
            }
        }
        if(intervals.size()==v.size())
        {
            return true;
        }
        return false;
        
    }
};

The time complexity is O(nlogn) and space complexity is O(n)

Sorting

what we do here is that we sort the array in ascending order. After sorting, we compare the meeting with the previous meeting and make sure that the meeting should not overlap. If it overlaps, return false otherwise return true.

class Solution {
    static bool compare(vector<int>v1, vector<int>v2) {
        return v1[0] == v2[0] ? v1[1] > v2[1] : v1[0] < v2[0];
    }
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        
        sort(intervals.begin(), intervals.end(), compare);
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i-1][1] > intervals[i][0])
                return false;
        }
        
        return true;
    }
};

The time Complexity is O(nlogn) and space complexity is O(1)

Please write to us if something is missing or wrong, we will be happy to fix it.

This article is contributed by Monika Bhasin

Largest sum of non-adjacent numbers

Given an array of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.For example,

Input:
[2, 4, 6, 2, 5] 
Output:
13
Explanation:
Since we pick 2, 6, and 5. 

Input:
[5, 1, 1, 5] 
Output:
10 
Explanation:
Since we pick 5 and 5.

Thought process

This problem is very similar to the coin change problem, where for each coin we make a decision, whether to include or exclude a coin in the change or not.

In this problem as well, we make the choice for each number. What if we include a number at index i in the sum and what if we do not include it? If we include the number in the sum, which eventually may be the maximum sum, what can we do with the remaining numbers in the array? If we include a[i], then we definitely cannot include a[i+1], due to the constraint of non-adjacent numbers. After making the choice that we will include a[i] into the sum, our problem reduces to find the maximum sum of non-adjacent numbers from index i+2 to a.length-1.

What if I do not include this number a[i] in the sum? In that case, we can choose a[i+1] in the sum, so the problem reduces to find the largest sum of non-adjacent numbers in the array from index i+1 to a.length

We do not know which choice (to include or exclude a[i]) will give us the largest sum, so we try both and take the maximum of both.

Recursive implementation

    public int sum(int[] a){
        return sumUtil(a,0);
    }

    private int sumUtil(int[] a, int index){
        if(index > a.length-1){
            return 0;
        }

        return Math.max(a[index] + sumUtil(a, index+2),
                    sumUtil(a, index+1)
        );
    }

For each number we take two choices and follow them, overall complexity of above implementation is O(2n) where n is the length of the array.
Let’s see the execution tree of the recursive implementation with one of the examples, it looks like this:

largest sum of non adjacent numbers

It is evident from the execution tree that there are many subproblems colored red, blue, and light blue as groups, which are solved again and again. This is called overlapping subproblems and is a necessary condition to think in dynamic programming terms. We already know that an optimal solution to subproblem leads to an optimal solution to the original problem, hence, we can apply the dynamic programming approach here.

The best way to avoid calculating subproblems, again and again, is to memorize what is already calculated, so let’s modify the code to use a cache, this approach is called a top-down approach.

Top down implementation

    public int sum(int[] a){
        int [] cache = new int[a.length];
        return sumUtil(a,0, cache);
    }

    private int sumUtil(int[] a, int index){
        if(index > a.length-1){
            return 0;
        }
        if (cache[index] > 0){
            return cache[index];
        }

        cache[index] = Math.max(a[index] + sumUtil(a, index+2),
                    sumUtil(a, index+1)
        );
        return cache[index];
    }

There will be a maximum n calls to the sumUtil() function, so time complexity reduces to O(n) along space complexity of O(n).

How can we implement the bottom-up solution for this problem? If we defined a 1D array dp[] where dp[i] represents the maximum sum which can be achieved till index i of array. To include a[i] into that sum, we have to look for maximum sum that can be achieved till index i-2 i.e dp[i-2]. If we exclude the index, then we get the maximum sum till index i-1 i.e dp[i-1]. We take whatever is the maximum.
Recurrece relation is as follows.

dp[i] = max(dp[i-2] + a[i], dp[i-1]);

Bottom up implementation

   private int sumDP(int[] a){
        if(a.length == 0) return 0;

        if(a.length == 1) return a[0];
        if(a.length == 2) return Math.max(a[0], a[1]);

        int [] dp = new int[a.length];

        dp[0] = a[0];
        dp[1] = Math.max(a[0], a[1]);

        int max = 0;
        for(int i=2; i<a.length; i++){
            dp[i] = Math.max(a[i] + dp[i-2], dp[i-1]);
            max = Math.max(max, dp[i]);
        }

        return max;
    }

The time complexity of bottom-up approach is also O(n) along space complexity of O(n).

Follow-up: Can you do this in constant space?

Is subsequence

Given a string s and a string t, check if s is subsequence of t. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not). For example:

Input:
s="ace" ,t= "abcde"
Output: 
True

Input:
s="aec" t="abcde"
Output: 
False

Approach

This problem looks similar to edit distance problem which can be solved using dynamic programming. The only difference is only deletions are allowed in this problem.

Recursive approach

What happens if we take a character at index i from string s and a character at index from string t? There are two possibilities: either these characters are equal or they are not equal. If the characters are equal, then we found the corresponding character in the target string, so we have to look for a remaining substring from index i+1 in s in substring in t from index j+1
What if the characters are not equal? In that case, we keep looking in substring of t from index j+1, but the index of s does not change, it remains at i, because we have not found the match for this character yet in the target string.

Implementation note: s.substring(1) actually get the substring of the string from the second character to the last character and achieves the increase in the indices as mentioned above.

 private boolean isSubsequenceUtil(String s, String t){
        
        if(s.length() == 0) return true;
        
        if(t.length() == 0) return false;
        
        return (s.charAt(0) == t.charAt(0)
                 && isSubsequenceUtil(s.substring(1), t.substring(1)))
            || isSubsequenceUtil(s, t.substring(1));
                
    }

If you run the above code in Leetcode, it will give you Time Limit Exceeded error, that becomes obvious when we draw the execution tree of the function, we will notice that we are solving the same problem multiple times.

Top down approach

The first thing we should do it to avoid solving the subproblem, again and again, that can be achieved using memorization. We introduce a caching place to store if we have solved the problem already and if yes, what was the result. If we already have solved the problem, we will just use the result and not solve the problem again. Below is the memorization code.

 private boolean isSubsequenceUtil(String s, String t, boolean[][] isKnown,
                                      boolean[][] value,
                                      int sIndex, int tIndex){
        
        if(s.length() == sIndex) return true;
        
        if(t.length() == tIndex) return false;
        
        if(isKnown[sIndex][tIndex]){
            return value[sIndex][tIndex];
        }
        
        value[sIndex][tIndex] = (s.charAt(sIndex) == t.charAt(tIndex)
                 && isSubsequenceUtil(s, t, isKnown, value, 
                             sIndex+1, tIndex+1))
            || isSubsequenceUtil(s, t, isKnown, value, sIndex, tIndex+1);
                
        isKnown[sIndex][tIndex] = true;
                                 
        return value[sIndex][tIndex];
    }

This code passes all the test cases at Leetcode. This approach is called a top-down approach in dynamic programming, where we start with the top, keep solving smaller problems until we find a solution for the original problem.

Bottom up approach

Since the optimal solution to the subproblems leads to optimal solution to the original problem, we can apply another approach called the bottom-up approach. In this approach, we start from the smallest possible problem and build our solution upwards.

What is the smallest problem possible in this case? If string s is empty and target string t is not empty, s is definitely a subsequence although an empty one.
So, if I create a two dimensional array where rows represent the number of characters in t and column represent number of characters in s, then I can initialize the first column (which represents zero length of the source string) as

for(int i=0; i<=t.length(); i++){
   dp[i][0] = true;
}

Other way around, what if string t is empty and string s is not empty, then there is no way possible string s can be subsequence of string t, this can be filled in the table as follows:

for(int i=0; i<=t.length(); i++){
    dp[0][i] = false;
}

What if we move up a bit, let’s say we have i characters in string t and j characters in string s. We compare the i-th character with j-th character and see if there are equal?
If they are equal and if string t with i-1 characters already has string s with j-1 characters as subsequence, then we can mark that string t with i characters has string s with j characters as subsequence too.

If the characters are not equal, then either string s with j characters should already be subsequence in i-1 characters of string t, or it cannot be a subsequence in i characters either.

dp[i][j]= t[i] == s[j] && dp[i-1][j-1] 
dp[i][j]= dp[i-1][j]

If we go through each character in both string. One implementation note, i and j represent the length of strings and not the index, that is why we compare characters at index i-1 and j-1 when solving for dp[i][j]. Also if length of t is less than length of s there is no way s can be subsequence of t.

     private boolean isSubsequenceUtilDP(String s, String t){
        
        boolean [][] dp = new boolean[t.length()+1][s.length()+1];
         
        for(int i=0; i<=t.length(); i++){
            dp[i][0] = true;
        }
        for(int j=1;j<=s.length(); j++){
            dp[0][j] = false;
        }
        
        for(int i=1; i<=t.length(); i++){
            for(int j=1; j<=s.length(); j++){
                if(i < j) dp[i][j] = false;
                  
                else {
                    dp[i][j] = t.charAt(i-1) == s.charAt(j-1) ?
                        dp[i-1][j-1]
                        : dp[i-1][j];
                }
            }
        }
                                 
        return dp[t.length()][s.length()];
    }

The time complexity of dynamic programming solution is O(n * m) where n and m are length of string t and s respectively. Also, there is additional space complexity of O(n * m).

We can reduce this complexity by using stack data structure as the relative position of characters in source and target string should remain same and matched characters can be deleted.

Using Stack

  1. Push the characters of source string in reverse order onto the stack.
  2. Iterate through the characters of the target string, and check if the character matches with the top element of the stack. If it matches, pop the element from the stack.
  3. Obtain the end result – If size of stack is zero, then it returns true, else false.
public boolean isSubsequence(String s, String t) {
         if(s.length()==0 && t.length() > 0)
            return true;

        if(s.length() > t.length())
            return false;

       Stack<Character> stack=new Stack<>();
        for(int i=s.length()-1;i >=0;i--)
            stack.push(s.charAt(i));

        for(int i=0; i < t.length();i++){
            if(!stack.isEmpty() && t.charAt(i)==stack.peek())
                stack.pop();
        }
        return stack.isEmpty();
    }

Time Complexity of the stack based solution is O(n + m) and the space Complexity isO(m), where n and m are length of string t and s respectively

The space complexity can be further reduced to O(1) by using two pointers approach.

Two Pointers

Take two pointers i which is used to traverse string t and j, which is used to traverse strings. Increment j whenever there is a match and compare the value of j with the length of source string at the end.

public boolean isSubsequence(String s, String t) 
{
        if(s.length() > t.length())
            return false;
        int i = 0, j = 0;
        while(i < t.length() && j < s.length()){
            if(t.charAt(i) == s.charAt(j))
                j++;
            i++;
        }
        if(j == s.length())
            return true;
        return false;
}

The time Complexity is O(n + m) and the space Complexity is O(1)

Please write to us if something is missing or wrong, we will be happy to fix it.

Rotten oranges problem

Rotten oranges problem goes like: In a given grid, each cell can have one of three values:

  • the value 0 representing an empty cell;
  • the value 1 representing a fresh orange;
  • the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten because rotting only happens 4-directionally.

rotten oranges

Thoughts

Rotting oranges problem offers a unique perspective on identifying a graph search problem. At first glance, it seems like the solution to the problem lies in changing the status of the given grid on multiple time steps while counting the steps and making sure that we come to a conclusion to our iterations, akin to solving a sudoku puzzle, where the state of the entire grid matters.

On further inspection though, we can see that we do not need to worry about the state of the entire grid, just the fresh oranges adjacent newly rotting oranges at each time step. We can consider the oranges as nodes of a graph, and the fresh oranges around them as connected to these nodes. We do not know the entire state of the graph beforehand, but we know that the adjacent nodes will expose themselves as time passes. This pushes us towards the idea of a Breadth-First Search, where we topologically move level by level through a graph.

This problem also has some interesting edge cases, with it being necessary to parse the graph to identify such cases:

Invalid grid return -1
Grid with all rotten oranges return 0
Grid with no rotten oranges and no fresh return 0
Grid with no rotten oranges and fresh present return -1
Grid post BFS with fresh oranges left return -1
Grid post BFS with all rotten oranges return count

Show me the implementation

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -&gt; int:
        # Make sure we have a valid grid
        if len(grid) &lt; 1 or len(grid[0]) &lt; 1:
            return -1
        sources = []
        ones = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 2:
                    sources.append((i, j))
                elif grid[i][j] == 1:
                    ones += 1
        if len(sources) == 0:
            # In case of no rotten oranges, return value depending 
            # on the state of the grid
            if ones == 0:
                return 0
            else:
                return -1
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        # Grid is initially at t = -1
        count = -1
        visited = set(sources)
        # End the BFS when there are no new sources left
        while len(sources) &gt; 0:
            count += 1
            newsources = []
            for source in sources:
                i, j = source
                grid[i][j] = 2
                for direction in directions:
                    row = i + direction[0]
                    col = j + direction[1]
                    # Make sure it is a valid row and column,
                    # It is not visited, and it is a fresh orange
                    if row &gt;= 0 and row &lt; len(grid) \
                       and col &gt;= 0 and col &lt; len(grid[0]) \
                       and (row, col) not in visited and grid[row][col] == 1:
                        newsources.append((row, col))
                        visited.add((row, col))
            sources = newsources
        # Make sure there are no fresh oranges left in the grid
        for i in grid:
            for j in i:
                if j == 1:
                    return -1
        return count

The runtime complexity of BFS is O(V + E), which in our scenario translates to moving to every node, i.e. O(n * m) where n and m are dimensions of the grid. The space complexity of BFS is O(V), which similarly as time complexity translates into O(n*m)

This article is contributed by Khushman Patel

Trapping rain water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after rain. For example,

Input: [0,1,0,2,1,0,1,3,2,1,2,1] 
Output: 6

trapping rain water

Basic thought

We know water stays at the highest level it is able to, and it always maintains the same flat surface. Using this, we can infer that we need to find holes in the elevation where water would be able to rest at a level. To calculate how much water these holes would need to store, we can see that we need to have elevations on both sides, and we also need to track how much space a particular hole would be able to trap the water. Fig below is an example of a hole which holds 4 units of water.

trap water

Upon further breakdown of these holes, we can notice that we do not need to track the entire hole to find the capacity it holds, but we can parse each unit of the hole individually. Thus, the amount of water in each unit of the hole is

min(leftHeight, rightHeight) - currentUnitHeight.

What remains now is to calculate the leftHeight and the rightHeight. We could parse through them individually to find these out, but we can see a general pattern here: The highest elevation to the left inclusive of the current unit will become the leftHeight, and the highest elevation to the right inclusive of the current unit will become the rightHeight. The problem has been greatly simplified into maintaining track of highest heights on both sides of every unit.

Brute force solution

From our observations in the previous section, the simplest brute force approach is to calculate the highest elevation on both sides of every unit, and sum them up together. Each unit takes O(n) time with this approach, and there are n units to calculate in total. Thus, this approach will take O(n2) time.

Show me the brute force implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0
        ans = 0
        for i in range(len(height)):
            left_max = 0
            right_max = 0
            for j in range(i + 1):
                left_max = max(left_max, height[j])
            for j in range(i, len(height)):
                right_max = max(right_max, height[j])
            ans += min(left_max, right_max) - height[i]
        return ans

Dynamic Programming approach

As we can see from the brute force solution, we calculate the leftHeight and the rightHeight multiple times for the same node, i.e. the problem has overlapping subproblems. Thus a dynamic programming approach should optimize the brute force approach further. We can store the leftHeight and rightHeight elements till each index we have iterated, and thus the water storage calculation for each unit will now take O(1) time. Overall, this approach passes over the array thrice, and thus has a runtime of O(n) with a space complexity of O(n).

Show me the dynamic programming implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0
        ans = 0
        left_max = [0] * len(height)
        right_max = [0] * len(height)
        left_max[0] = height[0]
        right_max[-1] = height[-1]
        for i in range(1, len(height)):
            left_max[i] = max(height[i], left_max[i - 1])
        for i in reversed(range(len(height) - 1)):
            right_max[i] = max(height[i], right_max[i + 1])
        for i in range(1, len(height) - 1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

Stacks

Since we need to keep track of the highest elevations up to a point, stacks are a good approach to perform this operation in one pass of the array. The basic idea is since we need to store the largest elevations in the stack, as we iterate through the array, we can find the amount of water stored till the currentHeight is higher than elements of the stack and move on to the next value, i.e. water stored will always be of a hole shape, thus we can find the amount of water that can be stored between two high values. This operation passes over the array once, and each element can only have two operations maximum: Pushing and popping from the stack, thus its time complexity is O(n). The space complexity will be O(n), in case the entire array is stored on the stack.

Show me the stack implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3: return 0 ans = 0 stack = [] for i in range(len(height)): while len(stack) > 0 and height[i] > height[stack[-1]]:
                top = stack.pop()
                if len(stack) == 0:
                    break
                # Distance between the larger value still in the 
                #stack with a hole the height of the top element 
                #and the current element
                distance = i - stack[-1] - 1
                # Water that can be stored is smaller 
                # heights between these bounds, and the height 
                # of the intermediate region between top of the stack 
                # and current index
                curr_height = min(height[i], height[stack[-1]]) - height[top]
                ans += distance * curr_height
            stack.append(i)
        return ans

Simple Optimization

Another way to approach the problem is that since we need to find the maximum elevations on either side to calculate the current water stored, we can calculate the global maximum in one pass, and once we have the index for the same, we can iterate to it and from it to the rest of the array knowing that we have one bounded measurement which is the highest elevation in the array. The time complexity for this operation is O(n), but there are two passes over the array(once to calculate global maximum, and once to calculate the water amount). The space complexity is O(1).

Show me the implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0
        ans = 0
        gMax = 0 # Global Max
        for i in range(len(height)):
            gMax = i if height[gMax] < height[i] else gMax
        lMax = 0 # Left max yet
        for i in range(1, gMax):
            lMax = i if height[lMax] <= height[i] else lMax
            ans += max(0, height[lMax] - height[i])
        lMax = len(height) - 1 # Right max yet
        for i in reversed(range(gMax, len(height) - 1)):
            lMax = i if height[lMax] <= height[i] else lMax
            ans += max(0, height[lMax] - height[i])
        return ans

This article is contributed by Khushman Patel

Longest subarray with sum at most k

Given an array of integers A[], find the length of the longest subarray with the sum at most k where k is an integer. For example:

Input:
A[] = [10, 5, 2, 7, 1, 9], 
k = 15
Output:
4
Explanation
longest subarray with sum at most K is [ 5, 2, 7, 1 ].

Input:
A[] = {-5, 8, -14, 2, 4, 12},
k = 5
Output:
5

Longest subarray with a sum k

First of all, if you are not aware of the fundamentals of a sliding window, I would strongly recommend reading: Sliding window concept

The question is how do we know that this is a sliding window problem? Two hints are present in the problem itself, first, we are looking for a subarray i.e. a window, and second, that window has a certain property i.e with a sum of elements at most k.

We will follow the standard pattern for the sliding window; define two pointers, left(l)and right(r). l shrinks the window whenever a property of the window is violated and r expands the window. Every time we expand the window, we add the number to the current sum. If the sum becomes greater than k, we note down the length of this window and update the maximum length if this greater than the previous length. Then we start shrinking the window and subtract the numbers from the sum until the sum is less or equal to k again.

Let’s take an example and see how it works.
Longest subarray with sum at most k

Show me the implementation

package AlgorithmsAndMe;

public class SubarrayWithSumK {
    public int lengthOfSubarray(int[] a, int k){
        int l = 0;
        int r = 0;

        int len = a.length;
        int max = 0;
        int currentSum = 0;

        while(r < len){
            currentSum += a[r];

            while(l < r && currentSum > k){
                max = Math.max(max, r -l);
                currentSum -= a[l];
                l++;
            }
            r++;
        }

        return max;
    }
}

The time complexity of the above code is linear i.e O(n) with O(1) space complexity.

If you are interested, there is another similar problem on Leetcode called Subarray Product Less Than K, you can try there.

Error loading source code.

Show me the answer

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
       
        int l = 0;
        int r = 0;

        if(k == 0) return 0;
        int len = nums.length;
        int count = 0;
        int currentProd = 1;

        while(r < len){
            currentProd *= nums[r];

            while(l <= r && currentProd >= k){
                currentProd /= nums[l];
                l++;
            }
            count += r - l + 1;
            r++;
        }
        
        return count;
    }
}

Interview coming up? Check out our full coding interview prep course. There’s a get-the-job-or-your-money-back guarantee, so it only costs money if it actually works.

As always, shoot me an email if there’s anything I can help with.

Remove duplicate characters

Given a string, remove consecutive duplicate characters from the string. For example:

Input:
S = "aabccacc"
Output:
"ba"

Input:
S = "accacc"
Output:
""

Solution for this problem is in the idea that we need two pointers, one to read a character and another to write a character.
In this case, let’s say we take two pointers, i and j, where i points to the index where next character will be written, whereas j will is the position of current character.

As String in most languages is an immutable object and we are planning to modify it, it is better idea to convert string to a character array. For each character at index j, we will copy it at index i. Check if the chars[i-1] and chars[i] are equal? If yes, we found consecutive duplicate characters.
If found duplicate characters, we will move i to i-2 to remove both instances of the character. If not, nothing changes.

Removed consecutive duplicates from string implementation

package AlgorithmsAndMe;

public class RemovedDuplicates {

    public String removeDuplicates(String s){

        char [] res =  s.toCharArray();
        int i = 0;
        int [] count = new int[res.length];
        for(int j=0; j<res.length; j++, i++){
            res[i] = res[j];

            if(i > 0 && res[i] == res[i-1]){
                i -=2;
            }
        }

        return String.valueOf(res).substring(0, i);

    }
}

Sometimes the same question is asked with k as parameters: given a string, remove all consecutive K duplicate characters.
For example:

Input:
S =  deeedbbcccbdaa, K = 3.
Output:
"aa"

The idea is the same, keep two pointers i and j, one for writing and another for reading. We will copy the character onto the index i. If the new character is the same as the previous character, we increment the count. If not, we reset the count. If count is equal to k, we remove all the instance of the character by moving i by k to the left.

package AlgorithmsAndMe;

public class RemovedDuplicates {

    public String removeDuplicates(String s, int k){

        char [] res =  s.toCharArray();
        int i = 0;
        int [] count = new int[res.length];
        for(int j=0; j<res.length; j++, i++){
            res[i] = res[j];

            count[i] = i>0 && res[i-1] == res[j] ? count[i-1] + 1 : 1;

            if(count[i] == k){
                i -=k;
            }
        }

        return String.valueOf(res).substring(0, i);

    }
}

The time complexity of both the implementations is O(n).

Number of islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Input:
11110
11010
11000
00000

Output: 1

The first challenge of this problem is to identify that this is a graph problem. To identify that, we have to look if cells of the matrix can represent nodes, and are there any relationship between cells that can act as edges of the graph?
One hint is to the relationship between the cells of the matrix. For example, in the island problem, 0s are water, and 1s are land. Land can be connected to land only which is adjacent to the land and a piece of land is isolated if surrounded by water from all four sides.

To find the number of islands in the matrix, we have to find the number of connected components in the graphs as explained above. Which traversal can we use to find the number of connected components of a graph? It is a depth-first search problem.

In this case, nodes seem to be the cells with value 1(land). Most of the time, in these kinds of problems, each cell of the matrix with a certain value is a node. If we have an n x m matrix, we are looking at n x m possible nodes. Also, here be aware that we are not interested in all the cells. Based on the problem statement, we can discard some cells. For example, in the island problem, we are interested in the cells which represent the land.

Now, what will be the edges? In these kinds of problems, a statement is given like an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. It means that a cell with value 1 is connected to neighbor cells only if they also contain 1.

Now that we know that cells containing 1 in the matrix are nodes of the graphs and connected to neighbors in they are also 1. To count the number of islands, all we have to do is find connected components in the graph. We reduced a matrix problem to a graph problem after all. Should we create an entire graph? Well no, at any point in time, we do not need the entire graph.

Number of islands implementation

public int numIslands(char[][] grid) {
int count = 0;
Set<Integer> visited = new HashSet&lt;&gt;();
int n = grid.length;

if(n &lt;=0) return 0;
int m = grid[0].length;

for(int i=0; i&lt;n; i++){
    for(int j=0; j&lt;m; j++){
        int cell = i * m + j;
        if(!visited.contains(cell) &amp;&amp; grid[i][j] == '1'){
            count++;
            dfs(i, j, visited, grid);
        }
    }
}
return count;
}

void dfs(int i, int j, Set<Integer> visited, char[][] a){
//Check if the node we are traversing is actually a valid node.
if(i&lt;0 || i&gt;=a.length 
      || j&lt;0 || j&gt;=a[0].length 
      || a[i][j] == '0') return;

int cell = i * a[0].length + j;
if(visited.contains(cell)) return;
visited.add(cell); 

//Visit neighbors
dfs(i+1, j, visited, a);
dfs(i-1, j, visited, a);
dfs(i, j+1, visited, a);
dfs(i, j-1, visited, a);
}

The complexity of the above code is O(n * m) where m and n are rows and columns of the matrix.

Critical Connections in a Network

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
critical connection is a connection that, if removed, will make some server unable to reach some other server.
For example,
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.
critical connections in a network

Before going through this solution, I would strongly recommend reading Tarjan’s algorithm and find bridges in a graph problem.

class Solution {
    int timer;

    List<List<Integer>> g;
      
    boolean [] visited;
    /* This map stores the time when the
    current node is visited
     */
    int [] tin;
    int [] low;
    
    void dfs(int u, int parent, 
                    List<List<Integer>> res ) {
        visited[u] = true;

        //Put the current timer.
        tin[u] = timer;
        //Low is the time of entry to start with
        low[u] = timer;

        timer++;

        /*
            Go through all the neighbors
         */
        for (int to : g.get(u)) {
            //If it is parent, nothing to be done
            if (to == parent) continue;

            /* If the neighbor was already visited
                get the minimum of the neighbor entry time
                or the current low of the node.
             */
            if (visited[to]) {
                low[u] = Math.min(low[u], tin[to]);
            } else {
                //Else do the DFS
                dfs(to, u, res);
                /*
                 Normal edge scenario,
                 take the minimum of low of the parent 
                  and the child.
                 */
                low[u] = Math.min(low[u], low[to]);

                /* If low of the child node is less than
                   time of entry of current node, then
                   there is a bridge.
                 */
                if (low[to] > tin[u]){
                   //List<Integer> l = new ArrayList<>();
                    List<Integer> l = 
                           Arrays.asList(new Integer[]{u, to});
                   res.add(l);
                }
            }
        }


    }

    public void findBridges(List<List<Integer>> res) {
        timer = 0;
        for(int i=0; i<g.size(); i++){
            if (!visited[i])
                dfs(i, -1, res);
        }
    }

  public List<List<Integer>> criticalConnections(int n, 
                             List<List<Integer>> connections) {
      

    g = new ArrayList<>(); 
      
    visited = new boolean[n];
    /* This map stores the time when the
    current node is visited
     */
    tin = new int[n];
    low = new int[n];
    
    Arrays.fill(visited, false);
    Arrays.fill(tin, n);
    Arrays.fill(low, n);
    
    for(int i=0; i<n; i++){
        g.add(new ArrayList<>());
    }
    for(List<Integer> l : connections){
          g.get(l.get(0)).add(l.get(1));  
          g.get(l.get(1)).add(l.get(0));   
      }
      
      List<List<Integer>> res = new ArrayList<>();
      findBridges(res);
    
      return res;
        
    }
}

The complexity of this code is O(V + E) where V is number of vertices and E is number of edges in the graph.

If you want help with interview preparations, please feel free to book a free demo session with us.

Maximum area rectangle in a histogram

A histogram is a diagram consisting of rectangles whose area is proportional to the frequency of a variable and whose width is equal to the class interval. Below is an example of a histogram.

maximum area rectangle in histogram

Given a histogram, whose class interval is 1, find maximum area rectangle in it. Let me explain the problem in more details.

In the histogram above, there are at least 6 rectangles with areas 2, 1,5,6,2, and 3. Are there more rectangles? Yes, we can make more rectangles by combining some of these rectangles. A few are shown below.

Apparently, the largest area rectangle in the histogram in the example is 2 x 5 = 10 rectangle. The task is to find a rectangle with maximum area in a given histogram. The histogram will be given as an array of the height of each block, in the example, input will be [2,1,5,6,2,3].

Maximum area rectangle: thoughts

First insight after looking at the rectangles above is: block can be part of a rectangle with a height less than or equal to its height. For each block of height h[i], check what all blocks on the left can be part of a rectangle with this block. All the blocks on the left side with a height greater than the current block height can be part of such a rectangle.
Similarly, all the blocks on the right side with a height greater than the current block height can be part of such a rectangle.
Idea is to calculate leftLimit and rightLimit and find the area (rightLimit - leftLimit) * h[i].
Check if this area is greater than previously known area, then update the maximum area else, continue to the next block.

class Solution {
    public int largestRectangleArea(int[] heights) {
        
        if(heights.length == 0) return 0;
        int maxArea = Integer.MIN_VALUE;

        for(int i=0; i<heights.length; i++){
            //Find the left limit for current block
            int leftLimit = findLeftLimit(heights, i);

            //Find the right limit for current block
            int rightLimit = findRightLimit(heights, i);

            int currentArea = (rightLimit - leftLimit-1) * heights[i];
            maxArea = Integer.max(maxArea, currentArea);
        }

        return maxArea;
    }

    private int findLeftLimit(int [] heights, int index){
        int j = index-1;
        while (j >= 0 && heights[j] >= heights[index]) j--;

        return j;
    }

    private int findRightLimit(int [] heights, int index){
        int j = index+1;
        while (j < heights.length && heights[j] >= heights[index])
            j++;

        return j;
    }
}

The time complexity of the implementation is O(n2); we will left and right of each block which will take n operations, we do it for n blocks and hence the complexity is quadratic. Can we optimize the time complexity?

If heights[j] >= heights[i] and leftLimit of index j is already known, can we safely say that it will also be the leftLimit of index i as well?
Can we say the same thing for rightLimit well? Answers to all the questions are yes. If we store the left and right limit for all indices already seen, we can avoid re-calculating them.

class Solution {
    public int largestRectangleArea(int[] heights) {
        
        if(heights.length == 0) return 0;

        int maxArea = Integer.MIN_VALUE;

        //Finds left limit for each index, complexity O(n)
        int [] leftLimit = getLeftLimits(heights);
        //Find right limit for each index, complexity O(n)
        int [] rightLimit = getRightLimits(heights);

        for(int i=0; i<heights.length; i++){
            int currentArea = 
                (rightLimit[i] - leftLimit[i] -1) * heights[i];
            maxArea = Integer.max(maxArea, currentArea);
        }

        return maxArea;
    }

    private int[] getLeftLimits(int [] heights){

        int [] leftLimit = new int[heights.length];
        leftLimit[heights.length-1] = -1;

        for(int i=0; i<heights.length; i++) {
            int j = i - 1;
            while (j >= 0 && heights[j] >= heights[i]) {
                j = leftLimit[j];
            }
            leftLimit[i] = j;
        }
        return leftLimit;
    }

    private int[] getRightLimits (int [] heights){

        int [] rightLimit = new int[heights.length];
        rightLimit[heights.length-1] = heights.length;

        for(int i=heights.length-2; i>=0; i--){
            int j = i+1;
            while(j<heights.length 
                      && heights[j] > heights[i]){
                j = rightLimit[j];
            }
            rightLimit[i] = j;
        }
        return rightLimit;
    }
}

The array leftLimitcontains at index i the closest index j to the left of i such that height[j] < height[i]. You can think about each value of the array as a pointer (or an arrow) pointing to such j for every i. How to calculate leftLimit[i]? Just point the arrow one to the left and if necessary just follow the arrows from there, until you get to proper j. The key idea here to see why this algorithm runs in O(n) is to observe that each arrow is followed at most once.

Largest area rectangle: stack-based solution

There is a classic method to solve this problem using the stack as well. Let’s see if we can build a stack-based solution using the information we already have. Let’s we do not calculate the area of the rectangle which includes the bar when we are processing it. When should we process it? Where should this bar be put on? If we want to create a rectangle with a height of this bar, we should find the left and right boundaries of such a rectangle. We should put this bar on a stack.
Now when you are processing bar j if height[j] is less than the bar on the top of the stack, we pop out the bar at the top. Why? Because this is the first bar on the right which has a height less than the height of the bar at top of the stack. This means if we want to make a rectangle with a height of the bar at the top of the stack, this index means the right boundary. This also gives away that all the blocks on the stack are in increasing order, as we never put a block which has a height less than the height of block at the top on to the stack. It means the next bar on the stack is the first bar which has a height lower than the bar at the top. To calculate the area of the rectangle with height as h[top], we need to take width as current index j - stack.peek() - 1

So the idea is that:

  1. For each bar, take its height as the rectangle’s height. Then find the left and right boundaries of this rectangle.
  2. The second top bar in the stack is always the first bar lower than the top bar on the stack on the left.
  3. The bar that j points to is always the first bar lower than the top bar in the stack on the right.
  4. After step 2 and 3, we know the left and right boundaries, then know the width, then know the area.
private int maxAreaUsingStack(int[] heights){

        Stack<Integer> s = new Stack<>();

        int maxArea = 0;
        for(int i=0; i<=heights.length; i++){
            //Handling the last case
            int h = i == heights.length ? 0 : heights[i];
            while(!s.empty() && h < heights[s.peek()]){
                int top = s.pop();
                int leftLimit = s.isEmpty() ? -1 : s.peek();
                int width = i-leftLimit-1;

                int area = width * heights[top];
                maxArea = Integer.max(area, maxArea);
            }
            s.push(i);
        }
        return maxArea;
    }
The time complexity of the code is O(n) with an additional space complexity of O(n) If you are preparing for a technical interview in companies like Amazon, Facebook, etc and want help with preparation, please register for a coaching session with us.