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

Example:

`Input:nums = [1,1,1], k = 2Output: 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 `k`. where `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.

Example:

`Input: houses = [1,4,8,10,20], k = 3Output: 5Explanation: 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 `target`.

You have to find two non-overlapping sub-arrays of `arr`each 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.

Example:

`Input: arr = [3,2,2,4,3], target = 3Output: 2Explanation: 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 `k`.

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.

Example:

`Input: bloomDay = [1,10,3,10,2], m = 3, k = 1Output: 3Explanation: 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 `k`elements.

Example:

`Input: arr = [4,3,1,1,3,3,2], k = 3Output: 2Explanation: 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.

Example:

`Input: "12"Output: 2Explanation: 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.

Example:

`Input:s: "cbaebabacd" p: "abc"Output:[0, 6]Explanation: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:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list.

Note:

Example:

`Input: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.

Without Trie

 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.

Example:

`Input: [23, 2, 4, 6, 7],  k=6Output: TrueExplanation: 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 `0` to `numCourses-1`.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: `[0,1]`

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example:

`Input: numCourses = 2, prerequisites = [[1,0],[0,1]]Output: falseExplanation: 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.

Example:

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

Written by