Blog

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.

Longest subarray without repeated numbers

Given an array, find the length of the longest subarray which has no repeating numbers.

Input: 
A = {1,2,3,3,4,5}
Output: 
3
Explanation: 
Longest subarray without any repeating elements are {1,2,3} & {3,4,5}.

Thought Process

1. Brute Force

In this approach, you will consider each subarray and then check whether that particular subarray contains no repeating elements or not. Right? So let’s find out how expensive this task would be? The complexity of generating subarray of an array would be O(n2), and when I will generate a particular subarray then I have to check whether the subarray contains unique elements(will use a map for this) or not, which will take O(n) time.

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

2. Sliding Window Solution

Sliding Window Technique is a method for finding subarrays in an array that satisfy given conditions. If you’re new to Sliding Window technique, visit this Sliding Window, it will be helpful for you. In Short words, I can say that maintaining a subset of items as our window, and resizing and moving that window until we find a solution.

We will use two pointers to construct our window. To expand the window, we have to increment the right pointer and to shrink the window we have to increment the left pointer.

We will increment the right pointer by 1 until the property of the subarray is not violated if the property gets violated, we have to shrink the window(means increment the left pointer by 1) till the subarray contains the repeating letters. We have to repeat this step until the value of the right pointer <= array Size.

  • Here, Property means the subarray should contain only the unique elements.

Initially, left and right pointers both are at 0th index.

  1. Add the value of arr[right] into the map.
    • After adding the value, if map[arr[right]] is 1, that is ok.
      Increment the right pointer by 1.
      Update the maxSize of the window variable.
    • After adding the value into map, if map[arr[right]] is 2, it means that our window contains repeating elements. Now, we have to shrink the window from left so that our window always contains the unique elements.
      Increment the left pointer and parallely decrement the value of the map[arr[left]]by 1.
      Do this thing until the value of the map[arr[right]]becomes 1.
  2. Repeat the 1st step, till the right < arraySize

Time Complexity – O(n), where n is the number of integers in the array.
Space Complexity – O(k), where k is the number of distinct integers in the input array. This also means k<=n, because in worst case, the whole array might not have any repeating integers so the entire array will be added to the map.

longest subarray without repeating numbers

Implementation

#include<bits/stdc++.h>;
using namespace std;
int lengthOfLongestSubarray(vector<int>v)
{
    if(v.size()==0)
    {
        return 0;
    }
    map<int,int> mapy;
    int left=0, right=0;
    int max_window=-1;

    for(right=0;right<v.size();right++)
    {
        int num=v[right];
        mapy[num]=mapy[num]+1;
        
        while(left < right && mapy[num] > 1){
           mapy[v[left]]=mapy[v[left]]-1;
           left=left+1;
        }
        //calculating max_length of window
        max_window=max(max_window,right-left+1);
    }
    return max_window;
}
main()
{
    vector<int>v={1,2,3,3,4,5};
    cout<<lengthOfLongestSubarray(v);
}

This post is contributed by Monika Bhasin.

Single number in an array

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Example 1:
Input: [2,2,1,3,4,3,5,4,5,]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4

Approach 1

You will be thinking it’s a very simple problem. What we all need to do is to take count of each distinct number and that number having count 1 will be our answer. We can achieve it by using a dictionary.

Time Complexity – 0(N)
Space Complexity – 0(N)

What if your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? It means you have to solve the problem in O(N) time complexity and constant space that means space complexity must be O(1).

Think of an approach before going into the post.

Let me tell you, have you ever heard of Bit Manipulation?

‘’ As the name suggests, it is a process of performing logical operations on bits to achieve the desired result.’’

To understand the bit manipulation let’s first have a look at Logical Bitwise Operators.

  1. AND (&)
  2. OR ( | )
  3. XOR (^)
  4. Left Shift (<<)
  5. Right Shift (>>)

In our particular problem, we will implement Bitwise XOR to get the desired result.

Properties of Bitwise XOR (^)–

  1. 0 ^ 0 = 0
  2. 0 ^ 1 = 1
  3. 1 ^ 0 = 1
  4. 1 ^ 1 = 0

If we observe the above operations we find that XOR of the same bits results in 0 and XOR of two different bit results into 1.

Now, Let’s have a look on some other examples –

  • 1 ^ 1 ^ 1 ^ 1 = 0
  • 2 ^ 2 = 0
  • 1 ^ 1 ^ 2 = 2
  • 2 ^ 3 ^ 4 ^ 3 ^ 2 = 4 (XOR operation is commutative and associative)

Now pause and observe the above examples very carefully.

Approach 2

So, If you observe carefully you will find that XOR of all those numbers appearing twice are being cancelled out and we are left with the number that appears only once. It clearly means if there are N numbers out of which N-1 numbers appears twice (or even number of times) and one number appear only once, then XOR of all numbers collectively results into that number which appears only once (See Examples 6, 7, 8) and as a result we will get our desired number.

As in example 8, 2 appears twice (so 2 ^ 2 = 0) and 3 appears twice (3 ^ 3 = 0) and 4 appears only once so as a consequence we will get 4 (0 ^ 0 ^ 4 = 4)

So in order to solve our particular problem we need to find XOR of all the numbers of array and and resultant XOR will be our answer.

Python Solution –

def singleNumber(Arr, n):
        ans=0
        for i in range(N):
            ans^=Arr[i]
        return ans

Steps-

  1. Iterate over all elements of array
  2. Find the XOR of all elements of array and store it into a variable ans.
  3. Return ans.

Complexities –

  1. Time Complexity – O(n)
  2. Space Complexity- O(1)

This article is contributed by Md Taslim Ansari

Cutting rods problem

Given a rod of length ‘n’ units and list of prices of pieces of lengths ‘1’ to ‘n’, the problem is to determine the maximum value that can be obtained by cutting the rod and selling the pieces.
For eg.

Input:
Rod is of length 4 and list of prices is:
Piece length 1 2 3 4
Price 2 5 7 8
Output:
10
Explanation:
The maximum value that can be obtained in this case is ‘10’ by cutting the rod in pieces of length {2, 2}.

Thought process

One might get tempted to use a Greedy approach for solving problems where we need to find either minimum or maximum values, but remember that for the Greedy approach one has to give proof of its correctness as it takes just a single example/test case to prove that Greedy approach fails. Hence in general such problems are solved using DP.
Solution Approach:
To find the maximum value using the price list and length of the rod, instead of considering the extremes (like we do in Greedy) from the given input, we consider all the input values. Meaning, in a Greedy approach one might consider cutting the rod in pieces with the highest available price only so that he can obtain the maximum value, but this approach fails in case of the example above.

Hence to find the maximum value we will consider cutting the rod in pieces of all possible lengths, i.e. for a rod of length ‘4’, if get_max_val(price_list, rod_length = 4) gives the maximum value, then:
We’ll first consider making a cut at length 1: This gives us a piece of length 1 and we can sell this piece to get value 2.
Now we are left with the remaining rod of length 4 – 1 = 3. The problem now reduces to finding the maximum value that can be obtained from a rod of length 3 with the same input price list. The total value that can be obtained in this configuration will be:

2 + get_max_val(price_list, rod_length = 3).

Similarly, we can make a cut at length 2: this gives us a piece of length 2 and we can sell this piece to get value 5.

Now we are left with the remaining rod of length 4 – 2 = 2. The problem now reduces to finding the maximum value that can be obtained from a rod of length 2 with the same input price list. The total value that can be obtained in this configuration will be:

5 + get_max_val(price_list, rod_length = 2).

Also, we can make a cut at length 3: This gives us a piece of length 3 and we can sell this piece to get value 7.

Now we are left with the remaining rod of length 4 – 3 = 1. The problem now reduces to finding the maximum value that can be obtained from the rod of length 1 with the same input price list. The total value that can be obtained in this configuration will be:

7 + get_max_val(price_list, rod_length = 1).

We can also sell the complete rod of length ‘4’ as it is, which will fetch us the total value => 8

For each sub-problem, we’ll take a similar approach of cutting the current piece of a rod into pieces of length ranging from ‘1’ to ‘current rod length’. We keep cutting the rod and solving the resulting sub-problems till the length of the rod reaches zero. While trying out these different configurations we will keep a track of the maximum of the total value of each configuration.

The approach discussed above shows that this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).

Let’s try to implement this using recursion:
C++:

#include <iostream>
#include <vector>
using namespace std;
 
int get_max_value(vector<int>& price_list, int  rod_length)
{
      if(rod_length <= 0)
            return 0;
      int max_value = 0;
      for(int i=0; i<rod_length; i++)
      {
            max_value = max(max_value, 
                    price_list[i] 
                  + get_max_value(price_list, rod_length - i - 1)
            );
      }
      return max_value;
}
 
int main(void)
{
      vector<int> price_list{2, 5, 7, 8};
      int rod_length = 4;
      cout<<get_max_value(price_list, rod_length)<<endl;      
      return 0;
}

Java:

import java.io.*;
 
class rod_cutting
{
    static int max(int a, int b)
    {
        return (a < b) ? b : a;
    }
    
    static int get_max_value(int price_list[], int rod_length)
    {
        if (rod_length <= 0)
            return 0;
            
        int max_value = 0;
        
        for(int i=0; i<rod_length; ++i)
        {
            max_value = max(max_value, 
                       price_list[i] 
                     + get_max_value(price_list, rod_length - i - 1)
            );
        }
        
        return max_value;
    }
    
    public static void main(String args[])
    {
        int price_list[] = new int[] {2, 5, 7, 8}; 
        int rod_length = price_list.length; 
        System.out.println(get_max_value(price_list, rod_length)); 
    }
};

But this recursive implementation has exponential time complexity. Let’s have a look at the function call tree to understand the reason behind this:
rod cutting problem

In this example of finding max value for a rod of length = 4 and a list of prices for its pieces, subproblems such as get_max_value(price_list, 2) and get_max_value(price_list, 1) are calculated repeatedly. Our recursive algorithm for this problem solves the same subproblem over and over rather than always generating new subproblems. These are called overlapping subproblems.
As the two properties required for using Dynamic Programming: optimal substructure and overlapping subproblems hold, we can use DP for this problem. Unlike recursion, Dynamic Programming uses a bottom-up approach.

Dynamic Programming Approach

In DP we start calculating from the bottom and move up towards the final solution. The solutions of all subproblems are stored in a 2D array / DP table so that they can be reused when required.

#include <iostream>
#include <vector>
using namespace std;
 
int get_max_value(vector<int>& price_list, int  rod_length)
{
    int dp_table[rod_length+1][rod_length+1] = {};
    
    for (int i = 1; i <= rod_length; i++)
    {
        for (int j = 1; j <= rod_length; j++) 
        {
            if(j >= i)
            {
                dp_table[i][j] = max(dp_table[i-1][j],
                    price_list[i-1] + dp_table[i][j-i]);
            }
            else
            {
                dp_table[i][j] = dp_table[i-1][j];
            }
        }
    }
    
    return dp_table[rod_length][rod_length];
}
 
int main(void)
{
      vector<int> price_list{2, 5, 7, 8};
      int rod_length = 8;
      court<< get_max_value(price_list, rod_length)<<endl;      
      return 0;
}

The time complexity of the solution is O(n2) along with space complexity of O(n2) Where n is rod length.

The space complexity of the DP code can be reduced by skipping storing solutions of each subproblem so that instead of a 2D array we can work with a 1D array.

With a 2D array, we were storing solutions for subproblems that have a particular rod length with a subset of given price_list, but instead of this for a particular rod length we can compare total values obtained from all subproblems and storing only the maximum value, this way using a 1D array suffices.
But also note that a question, if asked, that what cuts were actually made to get the maximum value, cannot be answered with a 1D array solution. In 2D array, we can traverse back starting from dp_table[rod_length][rod_length] and check if the value at the current cell is calculated from the same row and if that’s the case then the current row number is considered as one of the piece lengths that were cut to get the maximum value.

import java.io.*;
 
class rod_cutting
{
    static int max(int a, int b)
    {
        return (a < b) ? b : a;
    }
    
    static int get_max_value(int price_list[], int rod_length)
    {
        int dp_table[] = new int[rod_length+1];
        dp_table[0] = 0;
        
        for (int i=1; i <= rod_length; ++i)
        {
            int max_value = 0;
            
            for (int j=0; j < i; ++j)
            {
                max_value = max(max_value, 
                     price_list[j] + dp_table[i - j - 1]);
            }
            dp_table[i] = max_value;
        }
        
        return dp_table[rod_length];
    }
    
    public static void main(String args[])
    {
        int price_list[] = new int[] {2, 5, 7, 8}; 
        int rod_length = price_list.length; 
        System.out.println(get_max_value(price_list, rod_length)); 
    }
};

The time complexity remains same O(n2) but the space complexity reduces to O(n) where n is rod length.

This article is contributed by Bhushan Aggrawal.

Subarrays with given sum

We are given an unsorted array containing positive and negative numbers, we need to find the number of subarrays with the given sum, k. For example,

Input: 
arr = [2, 4, -5, -5, 6] and k = -10
Output: 
1
Explanation: 
We can see that there is only one subarray (index 2 to 3) whose sum is -10. 

Thought process

If the sum of elements in the range [0, i] and [0, j] is the same, then we can say that the sum between [i + 1, j] will be zero. This statement will be more clear after understanding the below example.

Let’s take arr = [2, 4, 4, -10, 4, 6, 5, 6]. Sum of elements in the range [0, 2] = 2 + 4 + 4 = 10
Sum of elements in the range [0, 5] = 2 + 4 + 4 + (-10) + 4 + 6 = 10

The above two sums are the same. Here,i= 2 and j = 5. Let’s check whether the sum in the range [3, 5] is 0 or not. Sum of elements in the range [3, 5] = -10 + 4 + 6 = 0

Hence, the statement explained above is true.

Read more here: subarray with sum zero

We can extend this idea to this question. The modified statement is as follows if the difference of the sum of elements in the range [0, j]and [0, i] is k, then we can say that the sum between [i + 1, j] is k. Mathematically,

If Sum[0, j] - Sum[0, i] = k, where j > i
Then, Sum[i + 1, j] = k or Sum[0, j] - k = Sum[0, i]

For each index j in the array, if we have seen Sum[0, j] – k in the past, then we have found the subarray. But how to achieve this?

Let’s number of elements in an array is n. So, we need to maintain sum[0, 0], sum[0, 1], sum[0,2], sum[0, 3] … sum[0, n].
These sums are known as prefix sum. If the same sum occurs many times, we store the frequency of occurrence. We can use a hashmap where the key will denote the sum and value will denote the frequency of occurrence.

Any corner cases? What if k = sum[0, j], where j is an index. For this, sum[0, j] – k is 0 and we will try to find if we have seen 0 as the sum in the past. To handle this case, we will insert one entry to map as a map[0] = 1.

Algorithm

1. For each index in the array.
      1.1 sum = sum in the range [0, i]
      1.2 Check if sum - k is already encountered in the array, 
      i.e have we encountered any array in the past whose 
      the sum is sum - k. 
      1.3 If yes, add the frequency of sum - k to answer.
2. Finally, put the sum in the map with frequency as 1 if the sum is not seen in the past. 
3. If the sum is seen in the past, update frequency as old frequency + 1.
4. Finally, print the answer.

Show me the implementation

// nums = given array
// k = sum
int subarraySum(vector<int>& nums, int k) {
    	int ans = 0;   // to store the final count
        int sum = 0;  // to store sum
   	
        // to store prefix sum along with frequency
    	map<int, int> map;  
    	map[0] = 1;  // for case like k = sum[0, i]
   	  
    	for(int i = 0; i < nums.size(); i++)
    	{
                // calculating sum in the range[0, i]
        	sum += nums[i];    
                 // if sum - k is alread seen 
        	if(map.find(sum - k) != map.end())            
            	    ans += map[sum - k]; // add frequency
       	 
                // if sum is not seen in the past
        	if(map.find(sum) == map.end())    
            	    map[sum] = 1;
        	else 
            	    map[sum] = map[sum] + 1;
    	}
   	 
    	return and;
}

Time Complexity of the implementation is O(n) along with the space Complexity of O(n).

This article is contributed by Mukul Vashishtha

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

Find friend groups

There are Nstudents in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if Ais a direct friend of B, and Bis a direct friend of C, then Ais an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students. For example,

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

Thought process

When we talk about the connections or relationships, we immediately will think of graph data structure. The node is the person and the edge is the relationship between two persons. So, first, we have to figure out whether it will be a directed graph or an undirected graph. In this problem, the friendship is a mutual relationship, thus the graph is undirected.

When you are reading this problem, the concept of Strongly Connected Components(SCC) will come into your mind. Ok, we will discuss why? If A is a friend of B, B is a friend of C, then A will be a friend of C. What does it mean? A is indirectly connected to C. It means that every friend can reach every other friend through a path if they are directly or indirectly connected. So in this way, they are forming a strong group or circle, in which every vertex is connected directly or indirectly in its group/circle. Notice that all friends (both direct and indirect), who should be in one friend circle are also in one connected component​ in the graph. 

A particular group of friends is a single component. In this problem we are going to find out how many components are there in the graph.

friend groups

When you make a graph out of it. It will be like this(see below fig). It means there are 3 friends circles.

friend-circle

We can solve this problem using 2 methods: depth first search and disjoint set method

Using Depth first traversal method

Finding connected components for an undirected graph is very easy. We can do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components

1. Initialize all nodes as not visited.
2. Initialize variable count as 1.
3. for every vertex 'v'.
       (i) If 'v' is unvisited
            Call DFS(v)
            count=count+1
DFS(v)
1. Mark 'v' as visited.
2. Do following for every unvisited neighbor `u`
      recursively call DFS(u)

DFS based approach implementation

class Solution {
Public:
    void DFS(int node,vector<vector<int>> edges,vecto<bool>visited)
    {
        int i;
        visited[node]=true;
        for(int i=0;i<edges[node].size();i++)
        {
            if(edges[node][i]==1 && node!=i && visited[i]==false)
            {
                DFS(i,edges,visited);
            }
        }
    }

    //Main Method
    int findCircleNum(vector<vector<int>> edges) {
        int i,j;
        
        int n=edges.size();
        int count=0;
        vector<bool>visited(m);
        
        //mark all the nodes as unvisited
        for(i=0;i<n;i++)
        {
            visited[i]=false;
        }
        
        for(i=0;i<n;i++)
        {
            if(visited[i]==false)
            {
                DFS(i,edges,visited);
                count=count+1;
            }
        }
        
        return count;
    }
};

Complexity

  • Time Complexity: Since we just go along the edges and visit every node, it will be O(n).
  • Space Complexity: O(n), to store the visited nodes.

Using Disjoint Sets(Union Find)

So, how to think that this problem is solved by Disjoint Sets(union-find algorithm)?

 The answer is simple because we need to keep track of the set of elements(here friends) partitioned into a number of non-overlapping subsets. Disjoint Sets(Union Find) always do this work very efficiently. We will use the Union by Rank algorithm to solve this problem.

If you haven’t heard of the Disjoint Sets. Go to this link and read about it.

To join two nodes, we will compare the rank of parents of both nodes.

  • If the rank is equal, we can make any one of the parent’s node as a parent and increment the rank of the parent node by 1.
  • If the rank is not same, then we can make the parent whose rank is greater than other.

graph breadth first traversal application

 

Let’s start solving this.

Union(1,2): 1 is a parent of itself and 2 is parent of itself. As both of them have different parents, so we have to connect them, and we will any of the parent as root, in this case we chose 1 and make it a parent.

friend groups

Union(2,1): 1 is a parent of itself and 1 is a parent of 2, as both of them have the same parents, already joined.

Union(3,4) :3 is a parent of itself and 4 is a parent of itself. Both of them have different parents, we need to join them.

Union(4,3): 3 is parent of itself and 3 is the parent of 4. Both of them have the same parents, already joined.

Union(4,5):   3 is the parent node of 4 and 5 is the parent node of 5. Since parents are different, we have to compare the rank of the parents of both 4 and 5 nodes. 3 has higher rank then 5, it will be parent of 5 .(Used Path Compression) as shown in the below fig.

Union(5,4): As now, 4 and 5 have the same parents, already joined. Last is the node 6 which connected to itself. So, nothing to do there. At the end of this exercise, we found that there are three different sets in the graph, and that is our answer of number of groups of friends in this graph or matrix.

Disjoint set based approach implementation

class Solution {
public:
    class Node
    {
        public:
            int data;
            Node*parent;
            int rank=0;
    };
    //make a set with only one element.
    void make(int data)
    {
        Node*node=new Node();
        node->data=data;
        node->parent=node;
        node->rank=0;
        mapy[data]=node;
        return;
    }
    map<int,Node*> mapy;
    //To return the address of the particular node having data as `data` 
    Node*find(int data)
    {
        auto k=mapy.find(data);
        if(k==mapy.end())
        {
            //There is no any node created, create the node
            make(data);
            return mapy[data];
        }
        else
        {
            return mapy[data];
        }
        return NULL;
    }
    /*Find the representative(parent) recursively and does path compression  
    as well*/
    Node*parents(Node*node)
    {
        if(node->parent==node)
        {
            return node;
        }
        return node->parent = parents(node->parent);
    }
    //Main Method
    int findCircleNum(vector<vector<int>>edges) {
        int i,j;
        
        vector<int> v;
        int m=edges.size();
        int n=edges[0].size();
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            {
                if(edges[i][j]==1)
                {
                    int a=i;
                    int b=j;
                    
                    
                    Node*A=find(a);
                    Node*B=find(b);
            
                    Node*PA=parents(A);
                    Node*PB=parents(B);
            
                    if(PA==PB)
                    {
                    }
                    else
                    {
                        if(PA->rank>=PB->rank)
                        {
                            //increment rank if both sets have Same rank
                            PA->rank=(PA->rank==PB->rank)?PA->rank+1:PA->rank;
                            PB->parent=PA;
                        }
                        else
                        {
                            PA->parent=PB;
                        }
                    }
                    
                    }
                }
            }
        
        int number=0;
        for(auto k: mapy)
        {
            if(k.second->parent==k.second)
            {
                number=number+1;
            }
        }
        return number;
    }
};

Complexity

  • Time Complexity: For each of the edge, we need to find the parents  and do the union, which is O(mlogn).
  • Space Complexity: We used a map to store the parent information, O(n).

This post is contributed by Monika Bhasin

Longest Mountain in Array

The mountain at index i in array arris defined such that

arr[i-N]..arr[i-1]< arr[i] > arr[i+1] arr[i+N] 

where i cannot be 0 and arr.length-1 which means that the index(i) cannot be at the extreme ends in the array (start and end of an array). Given an array A of integers, return the length of the longest mountain.  Return 0 if there is no mountain. Minimum length of a mountain subarray should 3.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Thought process

Question is to find the mountain which has longest length which means the length of the increasing array ending at arr[i] + the length of the decreasing array starting at arr[i] should be longest among all the mountains in an array, then we can return that length as longest mountain length.

Also if there is a flattening curve as in case of [2,3,3] there is no peak, the flat curve will not be a part of a mountain. The answer for [2,3,3] is 0. Here are couple of inputs and expected answers. This is a good clarifying question in an interview.

Idea is that for each index i, we will keep a track of how many numbers are there towards the left of the indexiare in increasing order and how many numbers on the right side of the index i, which are in decreasing order. If the length of the mountain with index i has its peak is longer than earlier seen mountains, we update the longest length.

It is important to note that both side subarray should be monotonically increasing and decreasing. As soon as we hit a flat curve (consecutive duplicates numbers), the duplicate elements can not part of the mountain array .

Also note that we jump the left to the next number to the mountain array, because no index in this mountain array will make a bigger mountain than the current one. See why?

show me the solution

 public int longestMountain(int[] arr) {
        
        if(arr==null || arr.length<3) return 0;
        
        int left=1;
        int len=arr.length-1;
        int ans=0;
        
       while(left<=len){
           
           int upHill=0;
           int downHill=0;
           
           // if there are duplicates on the left ,
           //they wont be the part of the mountain
           while(left<=len && arr[left]==arr[left-1]) left++;
           
           while(left<=len && arr[left]>arr[left-1]) {
               upHill++;
               left++;
           }
           
           while(left<=len && arr[left]<arr[left-1]) {
               downHill++;
               left++;
           }
           
           // if the sequence is 2, 3, 3, 5 , then the 
           // downHill will not be greter than 0 at left = 2
           if(upHill>0 && downHill>0) {
               ans=Math.max(ans,upHill+downHill+1);
           }
           
       }
        return ans;
    }

The time complexity of the implementation is O(n)

.

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