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.

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).

Three Sum Problem

Given an array nums of n integers, are there elements a, b,c in nums such that a+ b + c= 0? Find all unique triplets in the array which gives the sum of zero.

The solution set must not contain duplicate triplets.

This problem is commonly known as three sum problem.

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

This problem is commonly asked in Amazon and Google interviews.

Three Sum problem : thought process

Before going into the details of find three numbers with a given sum, do you know how to find two numbers with a given sum s? The idea is simple, we keep a map of all the numbers in we already seen, if see a number a[i], we see in the map if S-a[i] is present or not. If yes, then we found the pair, if not, we put a[i] and move forward.

This solution has linear time complexity i.e O(n) with a space complexity of O(n) as well. There is a way to avoid space complexity by sorting the input array first and using two pointer approach.

Details of 2 sum problem, you can read here: 2 Sum problem: Find pair with given sum in array

Can we use our understanding of the two-sum problem to solve this three-sum problem?

Hint 1:
What happens if we take one number from the array and say that this number will be one of the three numbers which add up to zero? What happens to our problem statement now?

Hint 2:
If you have decided that A[0] will be part of three numbers which add up to zero, all we need is two find out two numbers from index 1..len-1 which add up to OA[0]. What does that mean? It looks like a 2-sum problem, doesn’t it?

Can you please explain more?
We will start with index i from 0 and len-1, each time claiming that A[i] is part of the solution. Once, we fixed A[i] in solution, we will find two numbers which add to 0-A[i] solution to that problem we already know. If we find those two numbers let’s say A[j] and A[k], then A[i],A[j] and A[k] from the triplet. If we do not find those two numbers, discard A[i] and move forward.
3 sum problem

Show me the implementation of three sum problem

class Solution {

        public List<List<Integer>> threeSum(int[] nums) {

            List<List<Integer>> result = new ArrayList<>();
            //O(n log n)
            Arrays.sort(nums);

         
            for(int i=0; i<nums.length; i++){ if (i > 0 && nums[i] == nums[i - 1]) {
                 continue;
                }
                if(nums[i] > 0) continue;
                int j = i+1;
                int k = nums .length -1;

                int target = 0-nums[i];
                /*
                 Below code is exactly the same to find 
                 two numbers with a given sum using two pointers
                */
                while(j<k){
                    if(nums[j] + nums[k] == target ){
                      /* If find j and k, such that element at 
                         index i, j and K add to zero, put them in result
                      */
                        ArrayList<Integer> triplet = new ArrayList<Integer>(
                            Arrays.asList(nums[i], nums[j], nums[k]));
                        j++;
                        k--;
                         while (j < k && nums[j] == nums[j - 1]) j++;  // skip same result
                         while (j < k && nums[k] == nums[k + 1]) k--; // skip same result //since we want only unique triplets, using set result.add(triplet); } else if(nums[j] + nums[k] > target){
                        k--;
                    }
                    else{
                        j++;
                    }

                }
            }
            return  result;
        } 
    }

If you do not come up with the idea of moving i, j and k to get unique triplets, it is OK. You can always use HashSet to filter out duplicates and then copy the HashSet to the result list. It will take more time but will give the correct result.

 if(uniqueSet.add(triplet)){
     result.add(triplet);
 }

The time complexity of the solution is O(n2) plus the complexity of sorting algorithm (never forget that to mention!!). However, sorting complexity is O(nlogn), hence the overall complexity is dominated by the quadratic expression.

Can you solve the following problems on the leetcode?
1. 3SUM
2. 3Sum Closest
3. Four sum problem.

Ship capacity problem

There are some problems which do not appear to be a binary search problem at first. For example, ship capacity problem on leetcode. Problem statement is:
A conveyor belt has packages that must be shipped from one port to another within D days.
The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

For example:

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed. 

Ship capacity problem and binary search algorithm

At first glance, it does not appear to be a binary search problem. Where is the input we will search on? That’s where we have to remember that to apply a binary search, we actually do not need an input set, all we need is lower and upper bound.

Hint 1
What is the minimum capacity you would need to ship this cargo? You can choose the lowest possible capacity if you infinite number of days to ship all weights.

Hint 2
What if you have only one day to ship all the weights? In that case, what will be the capacity of the ship? Do you need more than capacity ever?

To find these bounds, try to vary the constraint to extremes. In the example of ship capacity, try to put the number of days constraints to an extreme. What if we had an infinite number of days to ship the cargo?

Can you please explain more?
In that case, we will need a ship that has at least capacity greater than equal to the heaviest weight cargo, as no matter how many days, we cannot move the cargo.

Again, what if I had only 1 day to ship the whole cargo? In that case, we need a ship that can take all the weights in 1 day, so ship capacity should be the sum of all the weights.

Now, we know the lower and upper bound of the ship, all we have to adjust the capacity and see if we can ship cargo in D days? Start with mid, see if we can. If yes, then try a smaller capacity. If not, then try greater capacity. All we are doing is find the first capacity between lower and upper bounds. It seems like the first occurrence problem now.

Understood the concept, you still need help with implementation? Please see the code below.

Ship capacity problem implementation

    public int shipWithinDays(int[] weights, int D) {
        
        int upperLimit = 0;
        int lowerLimit = 0;
        
        for(int i = 0; i<weights.length; i++){
            upperLimit+= weights[i];
        }
        //Not returning from while loop :)
        while(lowerLimit < upperLimit){
            int shipCapacity = lowerLimit + (upperLimit - lowerLimit)/2;
            
            if(isItPossible(D, shipCapacity, weights)){
                upperLimit = shipCapacity;
            }
            else{
                lowerLimit = shipCapacity + 1;
            }
        }
        
        return lowerLimit;
        
    }
    
    private boolean isItPossible(int D, int shipCapacity, int[] weights){
        
        int currentLoad = 0;
        int days = 1;
        int i = 0;
        
        while(i<weights.length){
            if(weights[i] > shipCapacity) return false;
            
            currentLoad+= weights[i];
            if(currentLoad == shipCapacity){
                days++; i++;
                currentLoad = 0;
            }
            else if(currentLoad > shipCapacity){
                days++;
                currentLoad = 0;
            }
            else{
                i++;
            }
        }
        
        return days <= D;
    }

The time complexity of the solution is O(nlogc) where n is number of weights and c is capacity range.

Please share if you find anything wrong or missing. If you are looking for coaching to prepare for your technical interviews, please book a free session with us.

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.

Minimum in sorted rotated array

In post find element in sorted rotated array, we discussed an algorithm based on binary search, to find a given key in sorted rotated array.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. You may assume no duplicate exists in the array.

To understand the problem, let’s understand what is a sorted array, and then what is sorted rotated array?

An array is called sorted where for all i and j such that i < j, A[i] <= A[j].
A rotation happens when the last element of an array is pushed at the start and all elements of array move right by one position. This is called as rotation by 1. If the new last element is also pushed to start again, all elements are moved to the right, it’s a rotation by 2, and so on.

minimum in rotated sorted array

Find minimum in sorted rotated array problem is asked during telephonic or online coding rounds of companies like Microsoft or Amazon.

Minimum in sorted rotated array and binary search algorithm

As always, first, come up with a brute force solution without worrying about any optimizations as of now. The simplest way would be to scan through the array and keep track of the minimum. The complexity of this method is O(n).

In the brute force solution, we did not use the fact that the array is sorted and then rotated. Let’s forget about rotation and concentrate only on the sorted part.

What is the minimum element in a sorted array? Obviously, it is the first element of the array. We see that all the elements on the right side of the minimum elements are greater than the minimum.

What will happen if start rotating array now, is the condition that all the elements on the right of the minimum element are greater than it still holds? Yes, it does. Either there will be no element on the right side of minimum or the will be definitely greater than it. So it is obvious, that the first element in the sorted part of the array is a candidate for the minimum element in a sorted rotated array, rest all can be discard.

What if we start with the middle element. How do I know that if array on the right side of it is sorted or not? What information comparison between the middle and end gives us?

If middle element is less than the last element, the array is sorted from index mid to end, in this case, we have to look for minimum on the left part including the mid
minimum in sorted rotated array

If the middle element will be greater than the last element, array on the right side is not sorted, there must be someplace in this right part, where the sorted array start, hence minimum element should be in the right part of the array.

find minimum in rotated array

When should we stop? Well, what is the minimum of an array with only one element? The element itself. We will also stop when there is only 1 element left.

Algorithm to find minimum in sorted rotated array

  1. Find mid = start + (end- start) /2
  2. See if mid is part of sorted array or not, check A[mid] < A[end]
  3. If yes, minimum should be on the left part
  4. If no, minimum should be on the right part

Minimum in sorted rotated array implementation

class Solution {
    public int findMin(int[] nums) {
        
        int start = 0;
        int end = nums.length-1; //O(1)
        int mid;
        
        while(start < end){
            mid = start + ((end - start)/2);
        
            if(nums[mid]<nums[end]){
                end = mid;
            }
            else{
                start = mid+1;
            }
        }
        
        return nums[start];
    }
}

The complexity of the algorithm to find minimum in a sorted rotated array is O(logn) because of binary search algorithm.

This problem is asked in many variations like find pivot in a sorted rotated array or find the number of rotations.

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.