Coding Notes

Smallest Subarray with a given sum (easy)

Problem Statement

Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists.

Example 1:

1
2
3

Input: [2, 1, 5, 2, 3, 2], S=7 
Output: 2
Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2].

Example 2:

1
2
3

Input: [2, 1, 5, 2, 8], S=7 
Output: 1
Explanation: The smallest subarray with a sum greater than or equal to '7' is [8].

Example 3:

1
2
3

Input: [3, 4, 1, 1, 6], S=8 
Output: 3
Explanation: Smallest subarrays with a sum greater than or equal to '8' are [3, 4, 1] or [1, 1, 6].

Solution

This problem follows the Sliding Window pattern and we can use a similar strategy as discussed in Maximum Sum Subarray of Size K. There is one difference though: in this problem, the size of the sliding window is not fixed. Here is how we will solve this problem:

1. First, we will add-up elements from the beginning of the array until their sum becomes greater than or equal to ‘S’.
2. These elements will constitute our sliding window. We are asked to find the smallest such window having a sum greater than or equal to ‘S’. We will remember the length of this window as the smallest window so far.
3. After this, we will keep adding one element in the sliding window (i.e. slide the window ahead), in a stepwise fashion.
4. In each step, we will also try to shrink the window from the beginning. We will shrink the window until the window’s sum is smaller than ‘S’ again. This is needed as we intend to find the smallest window. This shrinking will also happen in multiple steps; in each step we will do two things:
   • Check if the current window length is the smallest so far, and if so, remember its length.
   • Subtract the first element of the window from the running sum to shrink the sliding window.

Java code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public int minSubArrayLen(int s, int[] nums) {
        int winSum=0;
        int minLength=Integer.MAX_VALUE;
        int winStart=0;
        for (int winEnd = 0; winEnd < nums.length; winEnd++) {
            // add the next element
            winSum+=nums[winEnd];
            // shrink the window as small as possible until the 'windowSum' is smaller than 'S'
            while (winSum>=s){
                minLength=Math.min(minLength,winEnd-winStart+1);
                winSum-=nums[winStart]; // subtract the element going out
                winStart++; // slide the window ahead
            }
        }
        return minLength==Integer.MAX_VALUE?0:minLength;
    }

Time Complexity

The time complexity of the above algorithm will be O(N). The outer for loop runs for all elements and the inner while loop processes each element only once, therefore the time complexity of the algorithm will be O(N+N) which is asymptotically equivalent to O(N).

Space Complexity

The algorithm runs in constant space O(1).

Longest Substring with K Distinct Characters (medium)

Problem Statement

Given a string, find the length of the longest substring in it with no more than K distinct characters.

Example 1:

1
2
3

Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".

Example 2:

1
2
3

Input: String="araaci", K=1
Output: 2
Explanation: The longest substring with no more than '1' distinct characters is "aa".

Example 3:

1
2
3

Input: String="cbbebi", K=3
Output: 5
Explanation: The longest substrings with no more than '3' distinct characters are "cbbeb" & "bbebi".

Solution

This problem follows the Sliding Window pattern and we can use a similar dynamic sliding window strategy as discussed in Smallest Subarray with a given sum. We can use a HashMap to remember the frequency of each character we have processed. Here is how we will solve this problem:

1. First, we will insert characters from the beginning of the string until we have ‘K’ distinct characters in the HashMap.
2. These characters will constitute our sliding window. We are asked to find the longest such window having no more than ‘K’ distinct characters. We will remember the length of this window as the longest window so far.
3. After this, we will keep adding one character in the sliding window (i.e. slide the window ahead), in a stepwise fashion.
4. In each step, we will try to shrink the window from the beginning if the count of distinct characters in the HashMap is larger than ‘K’. We will shrink the window until we have no more than ‘K’ distinct characters in the HashMap. This is needed as we intend to find the longest window.
5. While shrinking, we’ll decrement the frequency of the character going out of the window and remove it from the HashMap if its frequency becomes zero.
6. At the end of each step, we’ll check if the current window length is the longest so far, and if so, remember its length.

Java code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public int minSubArrayLen(int s, int[] nums) {
        int winSum=0;
        int minLength=Integer.MAX_VALUE;
        int winStart=0;
        for (int winEnd = 0; winEnd < nums.length; winEnd++) {
            // add the next element
            winSum+=nums[winEnd];
            // shrink the window as small as possible until the 'windowSum' is smaller than 'S'
            while (winSum>=s){
                minLength=Math.min(minLength,winEnd-winStart+1);
                winSum-=nums[winStart]; // subtract the element going out
                winStart++; // slide the window ahead
            }
        }
        return minLength==Integer.MAX_VALUE?0:minLength;
    }

Time Complexity

The time complexity of the above algorithm will be O(N)O(N) where ‘N’ is the number of characters in the input string. The outer for loop runs for all characters and the inner while loop processes each character only once, therefore the time complexity of the algorithm will be O(N+N)O(N+N) which is asymptotically equivalent to O(N)O(N).

Space Complexity

The space complexity of the algorithm is O(K)O(K), as we will be storing a maximum of ‘K+1’ characters in the HashMap.

No-repeat Substring (hard)

Problem Statement

Given a string, find the length of the longest substring which has no repeating characters.

Example 1:

1
2
3

Input: String="abccde"
Output: 3
Explanation: Longest substrings without any repeating characters are "abc" & "cde".

Example 2:

1
2
3

Input: String="abbbb"
Output: 2
Explanation: The longest substring without any repeating characters is "ab".

Example 3:

1
2
3

Input: String="aabccbb"
Output: 3
Explanation: The longest substring without any repeating characters is "abc".

Solution 

This problem follows the Sliding Window pattern and we can use a similar dynamic sliding window strategy as discussed in Longest Substring with K Distinct Characters. We can use a HashMap to remember the last index of each character we have processed. Whenever we get a repeating character we will shrink our sliding window to ensure that we always have distinct characters in the sliding window.

Java code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int winStart=0;
        int maxLength=0, curLength=0;
        Map<Character,Integer> p=new HashMap<>();
        char[] c=s.toCharArray();
        // try to extend the range [windowStart, windowEnd]
        for (int winEnd = 0; winEnd < c.length; winEnd++) {
            // if the map already contains the 'c[winEnd]', shrink the window from the beginning so that
            // we have only one occurrence of 'c[winEnd]'
            if (p.containsKey(c[winEnd])){
                // this is tricky; in the current window, we will not have any 'c[winEnd]' after its previous index
                // and if 'windowStart' is already ahead of the last index of 'c[winEnd]', we'll keep 'windowStart'
                winStart=Math.max(winStart,p.get(c[winEnd])+1);

            }
            p.put(c[winEnd],winEnd);// insert the 'c[winEnd]' into the map
            maxLength=Math.max(maxLength,winEnd-winStart+1);// remember the maximum length so far
        }
        return maxLength;
    }
}

Time Complexity 

The time complexity of the above algorithm will be O(N) where ‘N’ is the number of characters in the input string.

Space Complexity 

The space complexity of the algorithm will be O(K) where K is the number of distinct characters in the input string. This also means K<=N, because in the worst case, the whole string might not have any repeating character so the entire string will be added to the HashMap. Having said that, since we can expect a fixed set of characters in the input string (e.g., 26 for English letters), we can say that the algorithm runs in fixed space O(1); in this case, we can use a fixed-size array instead of the HashMap.

Remove Duplicates (easy)

Problem Statement 

Given an array of sorted numbers, remove all duplicates from it. You should not use any extra space; after removing the duplicates in-place return the new length of the array.

Example 1:

1
2
3

Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: The first four elements after removing the duplicates will be [2, 3, 6, 9].

Example 2:

1
2
3

Input: [2, 2, 2, 11]
Output: 2
Explanation: The first two elements after removing the duplicates will be [2, 11].

Solution 

In this problem, we need to remove the duplicates in-place such that the resultant length of the array remains sorted. As the input array is sorted, therefore, one way to do this is to shift the elements left whenever we encounter duplicates. In other words, we will keep one pointer for iterating the array and one pointer for placing the next non-duplicate number. So our algorithm will be to iterate the array and whenever we see a non-duplicate number we move it next to the last non-duplicate number we’ve seen.

Time Complexity 

The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.

Space Complexity 

The algorithm runs in constant space O(1).

Similar Questions 

Problem 1: Given an unsorted array of numbers and a target ‘key’, remove all instances of ‘key’ in-place and return the new length of the array.

Example 1:

1
2
3

Input: [3, 2, 3, 6, 3, 10, 9, 3], Key=3
Output: 4
Explanation: The first four elements after removing every 'Key' will be [2, 6, 10, 9].

Example 2:

1
2
3

Input: [2, 11, 2, 2, 1], Key=2
Output: 2
Explanation: The first two elements after removing every 'Key' will be [11, 1].

Solution:This problem is quite similar to our parent problem. We can follow a two-pointer approach and shift numbers left upon encountering the ‘key’. Here is what the code will look like:

Time and Space Complexity: The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.

The algorithm runs in constant space O(1).

Squaring a Sorted Array (easy)

Problem Statement 

Given a sorted array, create a new array containing squares of all the number of the input array in the sorted order.

Example 1:

1
2

Input: [-2, -1, 0, 2, 3]
Output: [0, 1, 4, 4, 9]

Example 2:

1
2

Input: [-3, -1, 0, 1, 2]
Output: [0 1 1 4 9]

Solution 

This is a straightforward question. The only trick is that we can have negative numbers in the input array, which will make it a bit difficult to generate the output array with squares in sorted order.

An easier approach could be to first find the index of the first non-negative number in the array. After that, we can use Two Pointers to iterate the array. One pointer will move forward to iterate the non-negative numbers and the other pointer will move backward to iterate the negative numbers. At any step, whichever number gives us a bigger square will be added to the output array. For the above-mentioned Example-1, we will do something like this:

Since the numbers at both the ends can give us the largest square, an alternate approach could be to use two pointers starting at both the ends of the input array. At any step, whichever pointer gives us the bigger square we add it to the result array and move to the next/previous number according to the pointer. For the above-mentioned Example-1, we will do something like this:

 Code:

Time complexity 

The time complexity of the above algorithm will be O(N) as we are iterating the input array only once.

Space complexity 

The space complexity of the above algorithm will also be O(N); this space will be used for the output array.

Triplet Sum to Zero (medium)

Problem Statement 

Given an array of unsorted numbers, find all unique triplets in it that add up to zero.

Example 1:

1
2
3

Input: [-3, 0, 1, 2, -1, 1, -2]
Output: [-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]
Explanation: There are four unique triplets whose sum is equal to zero.

Example 2:

1
2
3

Input: [-5, 2, -1, -2, 3]
Output: [[-5, 2, 3], [-2, -1, 3]]
Explanation: There are two unique triplets whose sum is equal to zero.

Solution 

This problem follows the Two Pointers pattern and shares similarities with Pair with Target Sum. A couple of differences are that the input array is not sorted and instead of a pair we need to find triplets with a target sum of zero.

To follow a similar approach, first, we will sort the array and then iterate through it taking one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ and ‘Z’ such that X + Y + Z == 0. At this stage, our problem translates into finding a pair whose sum is equal to “-X” (as from the above equation Y + Z == -X).

Another difference from Pair with Target Sum is that we need to find all the unique triplets. To handle this, we have to skip any duplicate number. Since we will be sorting the array, so all the duplicate numbers will be next to each other and are easier to skip.

Time complexity 

Sorting the array will take O(N * logN)O The searchPair() function will take O(N). As we are calling searchPair() for every number in the input array, this means that overall searchTriplets() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).

Space complexity 

Ignoring the space required for the output array, the space complexity of the above algorithm will be O(N) which is required for sorting.

Triplet Sum Close to Target (medium)

Problem Statement 

Given an array of unsorted numbers and a target number, find a triplet in the array whose sum is as close to the target number as possible, return the sum of the triplet. If there are more than one such triplet, return the sum of the triplet with the smallest sum.

Example 1:

1
2
3

Input: [-2, 0, 1, 2], target=2
Output: 1
Explanation: The triplet [-2, 1, 2] has the closest sum to the target.

Example 2:

1
2
3

Input: [-3, -1, 1, 2], target=1
Output: 0
Explanation: The triplet [-3, 1, 2] has the closest sum to the target.

Example 3:

1
2
3

Input: [1, 0, 1, 1], target=100
Output: 3
Explanation: The triplet [1, 1, 1] has the closest sum to the target.

Solution 

This problem follows the Two Pointers pattern and is quite similar to Triplet Sum to Zero.

We can follow a similar approach to iterate through the array, taking one number at a time. At every step, we will save the difference between the triplet and the target number, so that in the end, we can return the triplet with the closest sum.

Time complexity 

Sorting the array will take O(N* logN). Overall searchTriplet() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).

Space complexity 

The space complexity of the above algorithm will be O(N) which is required for sorting.

Triplets with Smaller Sum (medium)

Problem Statement 

Given an array arr of unsorted numbers and a target sum, count all triplets in it such that arr[i] + arr[j] + arr[k] < target where i, j, and k are three different indices. Write a function to return the count of such triplets.

Example 1:

1
2
3

Input: [-1, 0, 2, 3], target=3 
Output: 2
Explanation: There are two triplets whose sum is less than the target: [-1, 0, 3], [-1, 0, 2]

Example 2:

1
2
3
4

Input: [-1, 4, 2, 1, 3], target=5 
Output: 4
Explanation: There are four triplets whose sum is less than the target: 
   [-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]

Solution 

This problem follows the Two Pointers pattern and shares similarities with Triplet Sum to Zero. The only difference is that, in this problem, we need to find the triplets whose sum is less than the given target. To meet the condition i != j != k we need to make sure that each number is not used more than once.

Following a similar approach, first we can sort the array and then iterate through it, taking one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ and ‘Z’ such that X + Y + Z < target. At this stage, our problem translates into finding a pair whose sum is less than “$ target – X$” (as from the above equation Y + Z == target – X). We can use a similar approach as discussed in Triplet Sum to Zero.

Time complexity 

Sorting the array will take O(N * logN). The searchPair() will take O(N). So, overall searchTriplets() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).

Space complexity 

Ignoring the space required for the output array, the space complexity of the above algorithm will be O(N)O(N) which is required for sorting if we are not using an in-place sorting algorithm.

Similar Problems 

Problem: Write a function to return the list of all such triplets instead of the count. How will the time complexity change in this case?

Solution: Following a similar approach we can create a list containing all the triplets.

Another simpler approach could be to check every triplet of the array with three nested loops and create a list of triplets that meet the required condition.

Time complexity 

Sorting the array will take O(N * logN). The searchPair(), in this case, will take O(N^2); the main while loop will run in O(N) but the nested for loop can also take O(N) – this will happen when the target sum is bigger than every triplet in the array.

So, overall searchTriplets() will take O(N * logN + N^3), which is asymptotically equivalent to O(N^3).

Space complexity 

Ignoring the space required for the output array, the space complexity of the above algorithm will be O(N) which is required for sorting.

Dutch National Flag Problem (medium)

Problem Statement 

Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array.

The flag of the Netherlands consists of three colors: red, white and blue; and since our input array also consists of three different numbers that is why it is called Dutch National Flag problem.

Example 1:

1
2

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

Example 2:

1
2

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

Solution 

The brute force solution will be to use an in-place sorting algorithm like Heapsort which will take O(N*logN). Can we do better than this? Is it possible to sort the array in one iteration?

We can use a Two Pointers approach while iterating through the array. Let’s say the two pointers are called low and high which are pointing to the first and the last element of the array respectively. So while iterating, we will move all 0s before low and all 2s after high so that in the end, all 1s will be between low and high.

Time complexity 

The time complexity of the above algorithm will be O(N) as we are iterating the input array only once.

Space complexity 

The algorithm runs in constant space O(1)

Start of LinkedList Cycle (medium)

Problem Statement 

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.

Solution 

If we know the length of the LinkedList cycle, we can find the start of the cycle through the following steps:

1. Take two pointers. Let’s call them pointer1 and pointer2.
2. Initialize both pointers to point to the start of the LinkedList.
3. We can find the length of the LinkedList cycle using the approach discussed in LinkedList Cycle. Let’s assume that the length of the cycle is ‘K’ nodes.
4. Move pointer2 ahead by ‘K’ nodes.
5. Now, keep incrementing pointer1 and pointer2 until they both meet.
6. As pointer2 is ‘K’ nodes ahead of pointer1, which means, pointer2 must have completed one loop in the cycle when both pointers meet. Their meeting point will be the start of the cycle.

We can use the algorithm discussed in LinkedList Cycle to find the length of the cycle and then follow the above-mentioned steps to find the start of the cycle.

Time Complexity 

As we know, finding the cycle in a LinkedList with ‘N’ nodes and also finding the length of the cycle requires O(N). Also, as we saw in the above algorithm, we will need O(N) to find the start of the cycle. Therefore, the overall time complexity of our algorithm will be O(N).

Space Complexity 

The algorithm runs in constant space O(1).

Happy Number (medium)

Problem Statement 

Any number will be called a happy number if, after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to number ‘1’. All other (not-happy) numbers will never reach ‘1’. Instead, they will be stuck in a cycle of numbers which does not include ‘1’.

Example 1:

1
2
3

Input: 23   
Output: true (23 is a happy number)  
Explanations: Here are the steps to find out that 23 is a happy number:

Example 2:

1
2
3

Input: 12   
Output: false (12 is not a happy number)  
Explanations: Here are the steps to find out that 12 is not a happy number:

Step ‘13’ leads us back to step ‘5’ as the number becomes equal to ‘89’, this means that we can never reach ‘1’, therefore, ‘12’ is not a happy number.

Solution 

The process, defined above, to find out if a number is a happy number or not, always ends in a cycle. If the number is a happy number, the process will be stuck in a cycle on number ‘1,’ and if the number is not a happy number then the process will be stuck in a cycle with a set of numbers. As we saw in Example-2 while determining if ‘12’ is a happy number or not, our process will get stuck in a cycle with the following numbers: 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89

We saw in the LinkedList Cycle problem that we can use the Fast & Slow pointers method to find a cycle among a set of elements. As we have described above, each number will definitely have a cycle. Therefore, we will use the same fast & slow pointer strategy to find the cycle and once the cycle is found, we will see if the cycle is stuck on number ‘1’ to find out if the number is happy or not.

Time Complexity 

The time complexity of the algorithm is difficult to determine. However we know the fact that all unhappy number eventually get stuck in the cycle: 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4

This sequence behavior tells us two things:

1. If the number NN is less than or equal to 1000, then we reach the cycle or ‘1’ in at most 1001 steps.
2. For N > 1000N>1000, suppose the number has ‘M’ digits and the next number is ‘N1’. From the above Wikipedia link, we know that the sum of the squares of the digits of ‘N’ is at most 9^2M9​2​​M, or 81M81M (this will happen when all digits of ‘N’ are ‘9’).

This means:

1. N1 <81M
2. As we know M = log(N+1)
3. Therefore: N1 < 81 * log(N+1)N1=> N1 = O(logN)

This concludes that the above algorithm will have a time complexity of O(logN).

Space Complexity 

The algorithm runs in constant space O(1).

Middle of the LinkedList (easy)

Problem Statement 

Given the head of a Singly LinkedList, write a method to return the middle node of the LinkedList.

If the total number of nodes in the LinkedList is even, return the second middle node.

Example 1:

1
2

Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 3

Example 2:

1
2

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Output: 4

Example 3:

1
2

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Output: 4

Solution 

One brute force strategy could be to first count the number of nodes in the LinkedList and then find the middle node in the second iteration. Can we do this in one iteration?

We can use the Fast & Slow pointers method such that the fast pointer is always twice the nodes ahead of the slow pointer. This way, when the fast pointer reaches the end of the LinkedList, the slow pointer will be pointing at the middle node.

Time complexity 

The above algorithm will have a time complexity of O(N) where ‘N’ is the number of nodes in the LinkedList.

Space complexity 

The algorithm runs in constant space O(1).

Insert Interval (medium)

Problem Statement 

Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

Example 1:

1
2
3

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]]
Explanation: After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].

Example 2:

1
2
3

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]]
Explanation: After insertion, since [4,10] overlaps with [5,7] & [8,12], we merged them into [4,12].

Example 3:

1
2
3

Input: Intervals=[[2,3],[5,7]], New Interval=[1,4]
Output: [[1,4], [5,7]]
Explanation: After insertion, since [1,4] overlaps with [2,3], we merged them into one [1,4].

Solution 

If the given list was not sorted, we could have simply appended the new interval to it and used the merge() function from Merge Intervals. But since the given list is sorted, we should try to come up with a solution better than O(N * logN)

When inserting a new interval in a sorted list, we need to first find the correct index where the new interval can be placed. In other words, we need to skip all the intervals which end before the start of the new interval. So we can iterate through the given sorted listed of intervals and skip all the intervals with the following condition:

1

intervals[i].end < newInterval.start

Once we have found the correct place, we can follow an approach similar to Merge Intervals to insert and/or merge the new interval. Let’s call the new interval ‘a’ and the first interval with the above condition ‘b’. There are five possibilities:

The diagram above clearly shows the merging approach. To handle all four merging scenarios, we need to do something like this:

1
2

    c.start = min(a.start, b.start)
    c.end = max(a.end, b.end)

Our overall algorithm will look like this:

1. Skip all intervals which end before the start of the new interval, i.e., skip all intervals with the following condition:

   1	intervals[i].end < newInterval.start

2. Let’s call the last interval ‘b’ that does not satisfy the above condition. If ‘b’ overlaps with the new interval (a) (i.e. b.start <= a.end), we need to merge them into a new interval ‘c’:

   1 2	c.start = min(a.start, b.start) c.end = max(a.end, b.end)

3. We will repeat the above two steps to merge ‘c’ with the next overlapping interval.

Time complexity 

As we are iterating through all the intervals only once, the time complexity of the above algorithm is O(N), where ‘N’ is the total number of intervals.

Space complexity 

The space complexity of the above algorithm will be O(N) as we need to return a list containing all the merged intervals.

Intervals Intersection (medium)

Problem Statement 

Given two lists of intervals, find the intersection of these two lists. Each list consists of disjoint intervals sorted on their start time.

Example 1:

1
2
3

Input: arr1=[[1, 3], [5, 6], [7, 9]], arr2=[[2, 3], [5, 7]]
Output: [2, 3], [5, 6], [7, 7]
Explanation: The output list contains the common intervals between the two lists.

Example 2:

1
2
3

Input: arr1=[[1, 3], [5, 7], [9, 12]], arr2=[[5, 10]]
Output: [5, 7], [9, 10]
Explanation: The output list contains the common intervals between the two lists.

Solution 

This problem follows the Merge Intervals pattern. As we have discussed under Insert Interval, there are five overlapping possibilities between two intervals ‘a’ and ‘b’. A close observation will tell us that whenever the two intervals overlap, one of the interval’s start time lies within the other interval. This rule can help us identify if any two intervals overlap or not.

Now, if we have found that the two intervals overlap, how can we find the overlapped part?

Again from the above diagram, the overlapping interval will be equal to:

1
2

    start = max(a.start, b.start)
    end = min(a.end, b.end) 

That is, the highest start time and the lowest end time will be the overlapping interval.

So our algorithm will be to iterate through both the lists together to see if any two intervals overlap. If two intervals overlap, we will insert the overlapped part into a result list and move on to the next interval which is finishing early.

Time complexity 

As we are iterating through both the lists once, the time complexity of the above algorithm is O(N + M), where ‘N’ and ‘M’ are the total number of intervals in the input arrays respectively.

Space complexity 

Ignoring the space needed for the result list, the algorithm runs in constant space O(1).

Conflicting Appointments (medium)

Problem Statement 

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

Example 1:

1
2
3

Appointments: [[1,4], [2,5], [7,9]]
Output: false
Explanation: Since [1,4] and [2,5] overlap, a person cannot attend both of these appointments.

Example 2:

1
2
3

Appointments: [[6,7], [2,4], [8,12]]
Output: true
Explanation: None of the appointments overlap, therefore a person can attend all of them.

Example 3:

1
2
3

Appointments: [[4,5], [2,3], [3,6]]
Output: false
Explanation: Since [4,5] and [3,6] overlap, a person cannot attend both of these appointments.

Solution 

The problem follows the Merge Intervals pattern. We can sort all the intervals by start time and then check if any two intervals overlap. A person will not be able to attend all appointments if any two appointments overlap.

Time complexity 

The time complexity of the above algorithm is O(N*logN), where ‘N’ is the total number of appointments. Though we are iterating the intervals only once, our algorithm will take O(N * logN) since we need to sort them in the beginning.

Space complexity 

The space complexity of the above algorithm will be O(N), which we need for sorting. For Java, Arrays.sort() uses Timsort, which needs O(N) space.

Similar Problems 

Problem 1: Given a list of appointments, find all the conflicting appointments.

Example:

1
2
3
4

Appointments: [[4,5], [2,3], [3,6], [5,7], [7,8]]
Output: 
[4,5] and [3,6] conflict. 
[3,6] and [5,7] conflict.

Find the Missing Number (easy)

Problem Statement 

We are given an array containing ‘n’ distinct numbers taken from the range 0 to ‘n’. Since the array has only ‘n’ numbers out of the total ‘n+1’ numbers, find the missing number.

Example 1:

1
2

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

Example 2:

1
2

Input: [8, 3, 5, 2, 4, 6, 0, 1]
Output: 7

Solution 

This problem follows the Cyclic Sort pattern. Since the input array contains unique numbers from the range 0 to ‘n’, we can use a similar strategy as discussed in Cyclic Sort to place the numbers on their correct index. Once we have every number in its correct place, we can iterate the array to find the index which does not have the correct number, and that index will be our missing number.

However, there are two differences with Cyclic Sort:

1. In this problem, the numbers are ranged from ‘0’ to ‘n’, compared to ‘1’ to ‘n’ in the Cyclic Sort. This will make two changes in our algorithm:
   • In this problem, each number should be equal to its index, compared to index + 1 in the Cyclic Sort. Therefore => nums[i] == nums[nums[i]]
   • Since the array will have ‘n’ numbers, which means array indices will range from 0 to ‘n-1’. Therefore, we will ignore the number ‘n’ as we can’t place it in the array, so => nums[i] < nums.length
2. Say we are at index i. If we swap the number at index i to place it at the correct index, we can still have the wrong number at index i. This was true in Cyclic Sort too. It didn’t cause any problems in Cyclic Sort as over there, we made sure to place one number at its correct place in each step, but that wouldn’t be enough in this problem as we have one extra number due to the larger range. Therefore, we will not move to the next number after the swap until we have a correct number at the index i.

Time complexity 

The time complexity of the above algorithm is O(n). In the while loop, although we are not incrementing the index i when swapping the numbers, this will result in more than ‘n’ iterations of the loop, but in the worst-case scenario, the while loop will swap a total of ‘n-1’ numbers and once a number is at its correct index, we will move on to the next number by incrementing i. In the end, we iterate the input array again to find the first number missing from its index, so overall, our algorithm will take O(n) + O(n-1) + O(n) which is asymptotically equivalent to O(n).

Space complexity 

The algorithm runs in constant space O(1).

Find all Missing Numbers (easy)

Problem Statement 

We are given an unsorted array containing numbers taken from the range 1 to ‘n’. The array can have duplicates, which means some numbers will be missing. Find all those missing numbers.

Example 1:

1
2
3

Input: [2, 3, 1, 8, 2, 3, 5, 1]
Output: 4, 6, 7
Explanation: The array should have all numbers from 1 to 8, due to duplicates 4, 6, and 7 are missing.

Example 2:

1
2

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

Example 3:

1
2

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

Solution 

This problem follows the Cyclic Sort pattern and shares similarities with Find the Missing Number with one difference. In this problem, there can be many duplicates whereas in ‘Find the Missing Number’ there were no duplicates and the range was greater than the length of the array.

However, we will follow a similar approach though as discussed in Find the Missing Number to place the numbers on their correct indices. Once we are done with the cyclic sort we will iterate the array to find all indices that are missing the correct numbers.

Time complexity 

The time complexity of the above algorithm is O(n).

Space complexity 

Ignoring the space required for the output array, the algorithm runs in constant space O(1).

Find the Duplicate Number (easy)

Problem Statement 

We are given an unsorted array containing ‘n+1’ numbers taken from the range 1 to ‘n’. The array has only one duplicate but it can be repeated multiple times. Find that duplicate number without using any extra space. You are, however, allowed to modify the input array.

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Solution 

This problem follows the Cyclic Sort pattern and shares similarities with Find the Missing Number. Following a similar approach, we will try to place each number on its correct index. Since there is only one duplicate, if while swapping the number with its index both the numbers being swapped are same, we have found our duplicate!

Time complexity 

The time complexity of the above algorithm is O(n).

Space complexity 

The algorithm runs in constant space O(1) but modifies the input array.

Similar Problems 

Problem 1: Can we solve the above problem in O(1) space and without modifying the input array?

Solution: While doing the cyclic sort, we realized that the array will have a cycle due to the duplicate number and that the start of the cycle will always point to the duplicate number. This means that we can use the fast & the slow pointer method to find the duplicate number or the start of the cycle similar to Start of LinkedList Cycle.

The time complexity of the above algorithm is O(n) and the space complexity is O(1).

Find all Missing Numbers (easy)

Problem Statement 

We are given an unsorted array containing numbers taken from the range 1 to ‘n’. The array can have duplicates, which means some numbers will be missing. Find all those missing numbers.

Example 1:

1
2
3

Input: [2, 3, 1, 8, 2, 3, 5, 1]
Output: 4, 6, 7
Explanation: The array should have all numbers from 1 to 8, due to duplicates 4, 6, and 7 are missing.

Example 2:

1
2

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

Example 3:

1
2

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

Solution 

This problem follows the Cyclic Sort pattern and shares similarities with Find the Missing Number with one difference. In this problem, there can be many duplicates whereas in ‘Find the Missing Number’ there were no duplicates and the range was greater than the length of the array.

However, we will follow a similar approach though as discussed in Find the Missing Number to place the numbers on their correct indices. Once we are done with the cyclic sort we will iterate the array to find all indices that are missing the correct numbers.

Time complexity 

The time complexity of the above algorithm is O(n).

Space complexity 

Ignoring the space required for the output array, the algorithm runs in constant space O(1).

Reverse a Sub-list (medium)

Problem Statement 

Given the head of a LinkedList and two positions ‘p’ and ‘q’, reverse the LinkedList from position ‘p’ to ‘q’.

Solution 

The problem follows the In-place Reversal of a LinkedList pattern. We can use a similar approach as discussed in Reverse a LinkedList. Here are the steps we need to follow:

1. Skip the first p-1 nodes, to reach the node at position p.
2. Remember the node at position p-1 to be used later to connect with the reversed sub-list.
3. Next, reverse the nodes from p to q using the same approach discussed in Reverse a LinkedList.
4. Connect the p-1 and q+1 nodes to the reversed sub-list.

Time complexity 

The time complexity of our algorithm will be O(N)O(N) where ‘N’ is the total number of nodes in the LinkedList.

Space complexity 

We only used constant space, therefore, the space complexity of our algorithm is O(1)O(1).

Similar Questions 

Problem 1: Reverse the first ‘k’ elements of a given LinkedList.

Solution: This problem can be easily converted to our parent problem; to reverse the first ‘k’ nodes of the list, we need to pass p=1 and q=k.

Problem 2: Given a LinkedList with ‘n’ nodes, reverse it based on its size in the following way:

1. If ‘n’ is even, reverse the list in a group of n/2 nodes.
2. If n is odd, keep the middle node as it is, reverse the first ‘n/2’ nodes and reverse the last ‘n/2’ nodes.

Solution: When ‘n’ is even we can perform the following steps:

1. Reverse first ‘n/2’ nodes: head = reverse(head, 1, n/2)
2. Reverse last ‘n/2’ nodes: head = reverse(head, n/2 + 1, n)

When ‘n’ is odd, our algorithm will look like:

1. head = reverse(head, 1, n/2)
2. head = reverse(head, n/2 + 2, n)

Reverse every K-element Sub-list (medium)

Problem Statement 

Given the head of a LinkedList and a number ‘k’, reverse every ‘k’ sized sub-list starting from the head.

If, in the end, you are left with a sub-list with less than ‘k’ elements, reverse it too.

Solution 

The problem follows the In-place Reversal of a LinkedList pattern and is quite similar to Reverse a Sub-list. The only difference is that we have to reverse all the sub-lists. We can use the same approach, starting with the first sub-list (i.e. p=1, q=k) and keep reversing all the sublists of size ‘k’.

Time complexity 

The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.

Space complexity 

We only used constant space, therefore, the space complexity of our algorithm is O(1).

Number Range (medium)

Problem Statement #

Given an array of numbers sorted in ascending order, find the range of a given number ‘key’. The range of the ‘key’ will be the first and last position of the ‘key’ in the array.

Write a function to return the range of the ‘key’. If the ‘key’ is not present return [-1, -1].

 public int[] searchRange(int[] nums, int target) {
        int[] res=new int[]{-1,-1};
        res[0]=result(nums,target,false);
        if (res[0]!=-1){
            res[1]=result(nums,target,true);
        }
        return res;

    }
public int result(int[] nums,int target, boolean RightOrLeft){
        int start=0;
        int end=nums.length-1;
        int index=-1;
        while (start<=end){
            int middle=start+(end-start)/2;
            if (target>nums[middle]){
                start=middle+1;
            }else if (target<nums[middle]){
                end=middle-1;
            }else {  //nums[target]==nums[middle],
                index=middle;
                if (RightOrLeft){
                    //start go meet end
                   start=middle+1;
                }else {
                    //end go meet start
                    end=middle-1;
                }
            }
        }
        return index;
    }

Search in a Sorted Infinite Array (medium)

Problem Statement: #

Given an infinite sorted array (or an array with unknown size), find if a given number ‘key’ is present in the array. Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.

Since it is not possible to define an array with infinite (unknown) size, you will be provided with an interface ArrayReader to read elements of the array. ArrayReader.get(index) will return the number at index; if the array’s size is smaller than the index, it will return Integer.MAX_VALUE.

static class ArrayReader{
        int[] arr;
        ArrayReader(int[] arr){
            this.arr=arr;
        }

        public int get(int index){
            if (index>=arr.length)
                return Integer.MAX_VALUE;
            return arr[index];
        }
    }

    static class SearchInfiniteSortedArray{
        public static int search(ArrayReader reader,int key){
            int start=0;
            int end=1;
            while (reader.get(end)<key){
                int newStart=end+1;
                end=end+(end-start+1)*2;
                start=newStart;
            }

            return binarySearch(reader,start,end,key);
        }

        public static int binarySearch(ArrayReader reader,int start,int end,int key){
            while (start<=end){
                int middle=start+(end-start)/2;
                if (key>reader.get(middle)){
                    start=middle+1;
                }else if (key<reader.get(middle)){
                    end=middle-1;
                }else {
                    return middle;
                }
            }
            return -1;
        }

    }

    public static void main(String[] args) {
        ArrayReader reader=new ArrayReader(new int[]{4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30});
        System.out.println(SearchInfiniteSortedArray.search(reader,16));
        System.out.println(SearchInfiniteSortedArray.search(reader,11));
        reader=new ArrayReader(new int[]{1,3,8,10,15});
        System.out.println(SearchInfiniteSortedArray.search(reader,15));
        System.out.println(SearchInfiniteSortedArray.search(reader,200));
    }

7. Minimum Difference Element (medium)

Problem Statement #

Given an array of numbers sorted in ascending order, find the element in the array that has the minimum difference with the given ‘key’.

static class MinimumDifference{
        public static int searchMinDiffElement(int[] arr,int key){
            int start=0;
            int end=arr.length-1;
            while (start<=end){
                int middle=start+(end-start)/2;
                if (key>arr[middle]){
                    start=middle+1;
                }else if (key<arr[middle]){
                    end=middle-1;
                }else {
                    return arr[middle];
                }
            }
            //start is out of bound
            if ((start>=arr.length)) return arr[end];
            //now start=end+1, compare these two to find closest one
            if (arr[start]-key>key-arr[end]){
                return arr[end];
            }else
                return arr[start];
        }
    }
    

public static void main(String[] args) {
        System.out.println(MinimumDifference.searchMinDiffElement(new int[]{4, 6, 10},7));
        System.out.println(MinimumDifference.searchMinDiffElement(new int[]{4, 6, 10},4));
        System.out.println(MinimumDifference.searchMinDiffElement(new int[]{1, 3, 8, 10, 15},12));
        System.out.println(MinimumDifference.searchMinDiffElement(new int[]{4, 6, 10},17));

    }

Bitonic Array Maximum (easy)

Problem Statement #

Find the maximum value in a given Bitonic array. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array arr[i] != arr[i+1].

Solution #

A bitonic array is a sorted array; the only difference is that its first part is sorted in ascending order and the second part is sorted in descending order. We can use a similar approach as discussed in Order-agnostic Binary Search. Since no two consecutive numbers are same (as the array is monotonically increasing or decreasing), whenever we calculate the middle, we can compare the numbers pointed out by the index middle and middle+1 to find if we are in the ascending or the descending part. So:

1. If arr[middle] > arr[middle + 1], we are in the second (descending) part of the bitonic array. Therefore, our required number could either be pointed out by middle or will be before middle. This means we will be doing: end = middle.
2. If arr[middle] <= arr[middle + 1], we are in the first (ascending) part of the bitonic array. Therefore, the required number will be after middle. This means we will be doing: start = middle + 1.

We can break when start == end. Due to the two points mentioned above, both start and end will be pointing at the maximum number of the bitonic array.

My solution :

static class MaxInBitonicArray{
        public static int findMax(int[] arr){
            int start=0;
            int end=arr.length-1;

            while (start<end){
                int middle=start+(end-start)/2;
                if (arr[middle]>arr[middle+1]){
                    end=middle; // in descending order, move right
                }else{
                    start=middle+1; // in ascending order, move left
                }
            }
            return arr[start];
        }
    }

public static void main(String[] args) {
        System.out.println(MaxInBitonicArray.findMax(new int[]{1, 3, 8, 12, 4, 2}));
        System.out.println(MaxInBitonicArray.findMax(new int[]{3, 8, 3, 1}));
        System.out.println(MaxInBitonicArray.findMax(new int[]{1, 3, 8, 12}));
        System.out.println(MaxInBitonicArray.findMax(new int[]{10, 9, 8}));

    }

Kth Smallest Number (easy)

Problem Statement #

Given an unsorted array of numbers, find Kth smallest number in it.

Please note that it is the Kth smallest number in the sorted order, not the Kth distinct element.

Note: For a detailed discussion about different approaches to solve this problem, take a look at Kth Smallest Number.

Example 1

Input: [1, 5, 12, 2, 11, 5], K = 3
Output: 5
Explanation: The 3rd smallest number is '5', as the first two smaller numbers are [1, 2].

Example 2

Input: [1, 5, 12, 2, 11, 5], K = 4
Output: 5
Explanation: The 4th smallest number is '5', as the first three small numbers are [1, 2, 5].

Example 3

Input: [5, 12, 11, -1, 12], K = 3
Output: 11
Explanation: The 3rd smallest number is '11', as the first two small numbers are [5, -1].

Solution:

class Solution {
    public int findKthSmallest(int[] nums, int k) {
       PriorityQueue<Integer> maxHeap=new PriorityQueue<>((x,y)->y-x);
        //add first k
        for (int i = 0; i < k; i++) {
            maxHeap.add(nums[i]);  //O(logK)
        }
        
        for (int i = k; i < nums.length ; i++) {
            if (nums[i]<maxHeap.peek()){
                maxHeap.poll();
                maxHeap.add(nums[i]);
            }
        }
        return maxHeap.peek();
    }
}

‘K’ Closest Points to the Origin (easy)

973. K Closest Points to Origin

Problem Statement #

Given an array of points in the a 2D2D2D plane, find ‘K’ closest points to the origin.

Example 1

Input: points = [[1,2],[1,3]], K = 1
Output: [[1,2]]
Explanation: The Euclidean distance between (1, 2) and the origin is sqrt(5).
The Euclidean distance between (1, 3) and the origin is sqrt(10).
Since sqrt(5) < sqrt(10), therefore (1, 2) is closer to the origin.

Example 2

Input: point = [[1, 3], [3, 4], [2, -1]], K = 2
Output: [[1, 3], [2, -1]]

Solution

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<int[]> minHeap=new PriorityQueue<>((x,y)->getDistance(y)-getDistance(x));
        int[][] res=new int[K][2];
        //add first K points
        for (int i = 0; i < K; i++) {
            minHeap.add(points[i]);
        }

        //traversal points to get K sizes minHeap.
        for (int i = K; i < points.length; i++) {
           
            if (getDistance(points[i])<getDistance(minHeap.peek())){             
                minHeap.poll();            
                minHeap.add(points[i]);
            }
        }
        res= new ArrayList<>(minHeap).toArray(new int[res.length][]);
         
        return res;
    }
    
    
    //calculate distance
    public int getDistance(int[] d){
        return (d[0]*d[0])+(d[1]*d[1]);
    }
    
    
}

Time complexity

The time complexity of this algorithm is (N∗logK) as we iterating all points and pushing them into the heap.

Space complexity

The space complexity will be O(K) because we need to store ‘K’ point in the heap.

Connect Ropes (easy)

1167. Minimum Cost to Connect Sticks

Problem Statement #

Given ‘N’ ropes with different lengths, we need to connect these ropes into one big rope with minimum cost. The cost of connecting two ropes is equal to the sum of their lengths.

Example 1

Input: [1, 3, 11, 5]
Output: 33
Explanation: First connect 1+3(=4), then 4+5(=9), and then 9+11(=20). So the total cost is 33 (4+9+20)

Example 2

Input: [3, 4, 5, 6]
Output: 36
Explanation: First connect 3+4(=7), then 5+6(=11), 7+11(=18). Total cost is 36 (7+11+18)

Example 3

Input: [1, 3, 11, 5, 2]
Output: 42
Explanation: First connect 1+2(=3), then 3+3(=6), 6+5(=11), 11+11(=22). Total cost is 42 (3+6+11+22)

Solution

In this problem, following a greedy approach to connect the smallest ropes first will ensure the lowest cost. We can use a Min Heap to find the smallest ropes following a similar approach as discussed in Kth Smallest Number. Once we connect two ropes, we need to insert the resultant rope back in the Min Heap so that we can connect it with the remaining ropes.

Code

class Solution {
        public int connectSticks(int[] sticks) {
            PriorityQueue<Integer> minHeap=new PriorityQueue<>();
            //add array to Heap
            for(int i:sticks) minHeap.add(i);

            int res=0;
            int tmp=0; //sum of two sticks
            while (minHeap.size()>1){
                //get sum
                tmp=minHeap.poll()+minHeap.poll();
                res+=tmp;
                //add sum into Heap
                minHeap.add(tmp);

            }
            return res;

        }
    }

Time complexity

Given ‘N’ ropes, we need O(N*logN) to insert all the ropes in the heap. In each step, while processing the heap, we take out two elements from the heap and insert one. This means we will have a total of ‘N’ steps, having a total time complexity of O(N*logN).

Space complexity

The space complexity will be O(N) because we need to store all the ropes in the heap.

Top ‘K’ Frequent Numbers (medium)

347. Top K Frequent Elements

Problem Statement

Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

Example 1

Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]
Explanation: Both '11' and '12' apeared twice.

Example 2

Input: [5, 12, 11, 3, 11], K = 2
Output: [11, 5] or [11, 12] or [11, 3]
Explanation: Only '11' appeared twice, all other numbers appeared once.

Solution

This problem follows Top ‘K’ Numbers. The only difference is that in this problem, we need to find the most frequently occurring number compared to finding the largest numbers.

We can follow the same approach as discussed in the Top K Elements problem. However, in this problem, we first need to know the frequency of each number, for which we can use a HashMap. Once we have the frequency map, we can use a Min Heap to find the ‘K’ most frequently occurring number. In the Min Heap, instead of comparing numbers we will compare their frequencies in order to get frequently occurring numbers

class Solution {
        public int[] topKFrequent(int[] nums, int k) {

            //order by value of map
            PriorityQueue<Map.Entry<Integer,Integer>> minHeap=new PriorityQueue<>((x,y)->x.getValue()-y.getValue());
            Map<Integer,Integer> p=new HashMap<>();

            // find the frequency of each number
            for(int num:nums){
                p.put(num,p.getOrDefault(num,0)+1);
            }

            // go through all numbers of the numFrequencyMap and push them in the minHeap, which will have
            // top k frequent numbers. If the heap size is more than k, remove the smallest (top) number
            for (Map.Entry<Integer,Integer> e:p.entrySet()){
                minHeap.add(e);
                if (minHeap.size()>k){
                    minHeap.poll();
                }
            }

            //heap to array
           int[] res=new int[k]; int i=0;
           while (k-->0){
               res[i++]=minHeap.poll().getKey();
           }

            return res;

        }
    }

Time complexity

The time complexity of the above algorithm is O(N+N*logK).

Space complexity

The space complexity will be O(N). Even though we are storing only ‘K’ numbers in the heap. For the frequency map, however, we need to store all the ‘N’ numbers.

Frequency Sort (medium)

451. Sort Characters By Frequency

Problem Statement #

Given a string, sort it based on the decreasing frequency of its characters.

Example 1:

Input: "Programming"
Output: "rrggmmPiano"
Explanation: 'r', 'g', and 'm' appeared twice, so they need to appear before any other character.

Example 2:

Input: "abcbab"
Output: "bbbaac"
Explanation: 'b' appeared three times, 'a' appeared twice, and 'c' appeared only once.

Solution

This problem follows the Top ‘K’ Elements pattern, and shares similarities with Top ‘K’ Frequent Numbers.

We can follow the same approach as discussed in the Top ‘K’ Frequent Numbers problem. First, we will find the frequencies of all characters, then use a max-heap to find the most occurring characters.

Java Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

 class Solution {
        public String frequencySort(String s) {
            
            //order by value of map
            PriorityQueue<Map.Entry<Character,Integer>> maxHeap=new PriorityQueue<>((x,y)->y.getValue()-x.getValue());
            Map<Character,Integer> p=new HashMap<>();

            // find the frequency of each character
            for(char c:s.toCharArray()){
                p.put(c,p.getOrDefault(c,0)+1);
            }

            // add all characters to the max heap
            maxHeap.addAll(p.entrySet());


            // build a string, appending the most occurring characters first
            StringBuilder res=new StringBuilder();
            while (!maxHeap.isEmpty()){
                for (int i = 0; i < maxHeap.peek().getValue(); i++) {
                    res.append(maxHeap.peek().getKey());
                }
                maxHeap.poll();
            }
            return res.toString();
        }
    }

Time complexity

The time complexity of the above algorithm is O(D*logD) where ‘D’ is the number of distinct characters in the input string. This means, in the worst case, when all characters are unique the time complexity of the algorithm will be O(N*logN) where ‘N’ is the total number of characters in the string.

Space complexity

The space complexity will be O(N), as in the worst case, we need to store all the ‘N’ characters in the HashMap.

Kth Largest Number in a Stream (medium)

703. Kth Largest Element in a Stream

Problem Statement #

Given a string, sort it based on the decreasing frequency of its characters.

Example 1:

1
2
3
4

Input: [3, 1, 5, 12, 2, 11], K = 4
1. Calling add(6) should return '5'.
2. Calling add(13) should return '6'.
2. Calling add(4) should still return '6'.

Solution

This problem follows the Top ‘K’ Elements pattern and shares similarities with Kth Smallest number.

We can follow the same approach as discussed in the ‘Kth Smallest number’ problem. However, we will use a Min Heap (instead of a Max Heap) as we need to find the Kth largest number.

Java Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class KthLargest {
        PriorityQueue<Integer> minHeap=new PriorityQueue<>((x,y)->x-y);
        final int k;
        // add the numbers in the min heap
        public KthLargest(int k, int[] nums) {
            this.k=k;
            for (int i = 0; i <nums.length; i++) {
                minHeap.add(nums[i]);
            }
        }
        // add the new number in the min heap
        public int add(int val) {
            minHeap.add(val);
            if (minHeap.size()>this.k){
                minHeap.poll();
            }

            // return the 'Kth largest number
            return minHeap.peek();

        }
    }

Time complexity

The time complexity of the add() function will be O(logK) since we are inserting the new number in the heap.

Space complexity

The space complexity will be O(K) for storing numbers in the heap.

‘K’ Closest Numbers (medium)

658. Find K Closest Elements  (PS: Contain repeated number)

Problem Statement #

Given a sorted number array and two integers ‘K’ and ‘X’, find ‘K’ closest numbers to ‘X’ in the array. Return the numbers in the sorted order. ‘X’ is not necessarily present in the array.

Example 1:

1
2

Input: [5, 6, 7, 8, 9], K = 3, X = 7
Output: [6, 7, 8]

Example 2:

1
2

Input: [2, 4, 5, 6, 9], K = 3, X = 6
Output: [4, 5, 6]

Example 3:

1
2

Input: [2, 4, 5, 6, 9], K = 3, X = 10
Output: [5, 6, 9]

Solution

This problem follows the Top ‘K’ Numbers pattern. The biggest difference in this problem is that we need to find the closest (to ‘X’) numbers compared to finding the overall largest numbers. Another difference is that the given array is sorted.

Utilizing a similar approach, we can find the numbers closest to ‘X’ through the following algorithm:

1. 1. Since the array is sorted, we can first find the number closest to ‘X’ through Binary Search. Let’s say that number is ‘Y’.
   2. The ‘K’ closest numbers to ‘Y’ will be adjacent to ‘Y’ in the array. We can search in both directions of ‘Y’ to find the closest numbers.
   3. We can use a heap to efficiently search for the closest numbers. We will take ‘K’ numbers in both directions of ‘Y’ and push them in a Min Heap sorted by their absolute difference from ‘X’. This will ensure that the numbers with the smallest difference from ‘X’ (i.e., closest to ‘X’) can be extracted easily from the Min Heap.
   4. Finally, we will extract the top ‘K’ numbers from the Min Heap to find the required numbers.

Java Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {

            //find the closest number in array
            int index=binarySearch(arr,x);
            int low=index-k;
            int high=index+k;
            low=Math.max(low,0); //make sure in bound
            high=Math.min(arr.length-1,high); //make sure in bound

            // add all candidate elements to the min heap, sorted by their absolute difference from 'X'
            PriorityQueue<Pair<Integer,Integer>> minHeap=new PriorityQueue<>((i, j)->i.getKey()-j.getKey());
            for (int i = low; i <=high ; i++) {
                minHeap.add(new Pair<>(Math.abs(arr[i]-x),arr[i]));
            }

            //the top 'K' elements having smallest deference from 'X'
            List<Integer> res=new ArrayList<>();
            for (int i = 0; i < k; i++) {
                res.add(minHeap.poll().getValue());
            }
            Collections.sort(res);

            return res;
        }

        public int binarySearch(int[] arr, int x){
            int start=0;
            int end=arr.length-1;
            while (start<end){
                int middle=start+(end-start)/2;
                if (x>arr[middle]){
                    start=middle+1;
                }else if (x<arr[middle]){
                    end=middle-1;
                }else {
                    return middle;
                }

            }
            if (start>arr.length) return arr.length-1;
            if (end<0) return 0;
            if (arr[start]-x>x-arr[end]){
                return end;
            }else return start;


        }
    }

Time complexity

The time complexity of the above algorithm is O(logN + K*logK). We need O(logN) for Binary Search and O(K*logK) to insert the numbers in the Min Heap, as well as to sort the output array.

Space complexity

The space complexity will be O(K), as we need to put a maximum of 2K numbers in the heap.

Sum of Elements (medium)

Problem Statement #

Given an array, find the sum of all numbers between the K1’th and K2’th smallest elements of that array.

Example 1:

1
2
3
4

Input: [1, 3, 12, 5, 15, 11], and K1=3, K2=6
Output: 23
Explanation: The 3rd smallest number is 5 and 6th smallest number 15. The sum of numbers coming 
between 5 and 15 is 23 (11+12).

Example 2:

1
2
3
4

Input: [3, 5, 8, 7], and K1=1, K2=4
Output: 12
Explanation: The sum of the numbers between the 1st smallest number (3) and the 4th smallest 
number (8) is 12 (5+7).

Example 3:

1
2

Input: [2, 4, 5, 6, 9], K = 3, X = 10
Output: [5, 6, 9]

Solution

This problem follows the Top ‘K’ Numbers pattern, and shares similarities with Kth Smallest Number.

We can find the sum of all numbers coming between the K1’th and K2’th smallest numbers in the following steps:

1. 1. First, insert all numbers in a min-heap.
   2. Remove the first K1 smallest numbers from the min-heap.
   3. Now take the next K2-K1-1 numbers out of the heap and add them.This sum will be our required output.

Java Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class SumOfElements{
    public int findSumOfElements(int[] nums,int k1,int k2){
        PriorityQueue<Integer> minHeap=new PriorityQueue<>((x,y)->x-y);

        // insert all numbers to the min heap
        for (int i = 0; i < nums.length; i++) {
            minHeap.add(nums[i]);
        }

        // remove k1 small numbers from the min heap
        for (int i = 0; i < k1; i++) {
            minHeap.poll();
        }
        // sum next k2-k1-1 numbers
        int res=0;
        for (int i = 0; i < k2-k1-1; i++) {
            res+=minHeap.poll();
        }
        return res;
    }
}

Time complexity

Since we need to put all the numbers in a min-heap, the time complexity of the above algorithm will be O(N*logN) where ‘N’ is the total input numbers.

Space complexity 

The space complexity will be O(N), as we need to store all the ‘N’ numbers in the heap.

Kth Smallest Number in M Sorted Lists (Medium)

378. Kth Smallest Element in a Sorted Matrixs  

Problem Statement #

Given ‘M’ sorted arrays, find the K’th smallest number among all the arrays.

Example 1:

1
2
3
4

Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4], K=5
Output: 4
Explanation: The 5th smallest number among all the arrays is 4, this can be verified from the merged 
list of all the arrays: [1, 2, 3, 3, 4, 6, 6, 7, 8]

Example 2:

1
2
3

Input: L1=[5, 8, 9], L2=[1, 7], K=3
Output: 7
Explanation: The 3rd smallest number among all the arrays is 7.

Solution

We can start merging all the arrays, but instead of inserting numbers into a merged list, we will keep count to see how many elements have been inserted in the merged list. Once that count is equal to ‘K’, we have found our required number.

We can start merging all the arrays, but instead of inserting numbers into a merged list, we will keep count to see how many elements have been inserted in the merged list. Once that count is equal to ‘K’, we have found our required number.

A big difference from Merge K Sorted Lists is that in this problem, the input is a list of arrays compared to LinkedLists. This means that when we want to push the next number in the heap we need to know what the index of the current number in the current array was. To handle this, we will need to keep track of the array and the element indices.

Java Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    class node{
        int elementIndex;
        int matrixIndex;

        public node(int matrixIndex, int elementIndex) {
            this.elementIndex = elementIndex;
            this.matrixIndex = matrixIndex;
        }
    }
    public int kthSmallest(int[][] matrix, int k) {

        PriorityQueue<node> minHeap=new PriorityQueue<>(Comparator.comparingInt(x -> matrix[x.matrixIndex][x.elementIndex]));

        // put the first value of each array to the min heap
        for (int i = 0; i < matrix.length; i++) {
            minHeap.add(new node(i,0));
        }

        int ct=0;
        while (!minHeap.isEmpty()){
            //poll one by one
            node cur=minHeap.poll();
            ct++;
            //Kth poll, return
            if (ct==k){
                return matrix[cur.matrixIndex][cur.elementIndex];
            }

            //add until last index of array
            if (cur.elementIndex+1<matrix[cur.matrixIndex].length){
                minHeap.add(new node(cur.matrixIndex,cur.elementIndex+1));
            }
        }

        //not found -1
        return -1;
    }
}

Time complexity

Since we’ll be going through at most ‘K’ elements among all the arrays, and we will remove/add one element in the heap in each step, the time complexity of the above algorithm will be O(K*logM) where ‘M’ is the total number of input arrays.

Space complexity

The space complexity will be O(M) because, at any time, our min-heap will be storing one number from all the ‘M’ input arrays.

Similar Problems 

Problem 1: Given ‘M’ sorted arrays, find the median number among all arrays.

Solution: This problem is similar to our parent problem with K=Median. So if there are ‘N’ total numbers in all the arrays we need to find the K’th minimum number where  K=N/2.

Problem 2: Given a list of ‘K’ sorted arrays, merge them into one sorted list.

Solution: This problem is similar to Merge K Sorted Lists except that the input is a list of arrays compared to LinkedLists. To handle this, we can use a similar approach as discussed in our parent problem by keeping a track of the array and the element indices.