Coding Problems and Solutions-5
 Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Input:nums = [1,1,1], k = 2
Approach — Use hash map to store the count of current sum ‘curr_sum’ from index i to len(arr)-1. At index i count the number of times we have encountered ‘curr_sum-k’. This will give the number of occurrences of sum = k starting at index i.
 Allocate Mailboxes — Given the array
houses and an integer
houses[i] is the location of the ith house along a street, your task is to allocate
k mailboxes in the street.
Return the minimum total distance between each house and its nearest mailbox.
Input: houses = [1,4,8,10,20], k = 3
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5
Approach — Sort the houses along x-axis. For i-th to j-th (i ≤ j) houses, the optimal position to place mailbox is at the middle house i.e. houses[(i+j)/2]. Compute the total distance of all houses from i to j from the mailbox position houses[(i+j)/2] and store it in dist_cache[i][j].
Then use recursion to place k mailboxes. After placing a mailbox between 0-th and i-th house, place the remaining k-1 mailboxes from i-th house onwards.
 Find Two Non-overlapping Sub-arrays Each With Target Sum — Given an array of integers
arr and an integer
You have to find two non-overlapping sub-arrays of
arreach with sum equal
target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.
Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.
Input: arr = [3,2,2,4,3], target = 3
Explanation: Only two sub-arrays have sum = 3 ( and ). The sum of their lengths is 2.
Approach — Use a hash map ‘suffix_sums’ to store the running sum from index i to len(arr)-1. For an index i, store the minimum length of sub-array in i to len(arr)-1 with sum ‘target’ in an array ‘width’. At index i check if ‘s-target’ is present in ‘suffix_sums’ then compute the minimum length and update in width[i].
Next in ‘prefix_sums’ repeat to check if ‘s-target’ is present at index i. If present then the current prefix length + width[i+1] is a possible candidate.
 Minimum Number of Days to Make ‘m’ Bouquets — Given an integer array
bloomDay, an integer
m and an integer
We need to make
m bouquets. To make a bouquet, you need to use
k adjacent flowers from the garden.
The garden consists of
n flowers, the
ith flower will bloom in the
bloomDay[i] and then can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make
m bouquets from the garden. If it is impossible to make
m bouquets return -1.
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
Approach — Use binary search. For number of days ‘d’, compute the maximum number of bouquets that can be made. If maximum number of bouquets is ≥ m then decrease ‘d’ else increase ‘d’.
 Least Number of Unique Integers after K Removals — Given an array of integers
arr and an integer
k. Find the least number of unique integers after removing exactly
Input: arr = [4,3,1,1,3,3,2], k = 3
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
Approach — Use greedy approach. Compute the counts of each integer and using a min-heap, remove the integer with the current minimum count first.
 Decode Ways — A message containing letters from
A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Approach — Use recursion.
 Find All Anagrams in a String — Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
s: "cbaebabacd" p: "abc"Output:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Approach — Precompute the character counts in ‘p’. Then using sliding window over ‘s’ of length len(p), check if the character counts over a window is same as that of p.
 Word Ladder — Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list.
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]Output: 5Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Trie based solution
Approach — Store the wordlist in a trie. Then use BFS. For a beginWord, at each position, replace it with ‘.’ and then search in trie if we can reach the end of a path and return all such strings. For all valid transformations update the BFS queue and continue.
IMP — Use Trie based approach if the wordList updates rarely and only the beginWord and endWord changes.
 Continuous Subarray Sum — Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.
Input: [23, 2, 4, 6, 7], k=6
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Approach — If (x+a)%k == x%k then a is divisible by k.
Use hash map to store running sum ‘s’ modulo k i.e. s%k for s from i to len(arr)-1. If for an index i, s%k has also been seen for some j > i it implies that arr[i:j] is divisible by k.
 Course Schedule — There are a total of
numCourses courses you have to take, labeled from
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Approach — Do DFS. If a cycle is found then return False else return True.
 Remove Nth Node From End of List — Given a linked list, remove the n-th node from the end of list and return its head.
Given linked list: 1->2->3->4->5, and n = 2.After removing the second node from the end, the linked list becomes 1->2->3->5.
Approach — Use 2 pointer approach. One pointer is n+1 distance behind than the other. When the forward pointer reaches the tail, the behind pointer is at the (n+1)-th node from end. Remove the next node of the behind pointer.