# Coding Problems and Solutions-5

[1] 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 = 2

**Output:** 2

(https://leetcode.com/problems/subarray-sum-equals-k/)

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.

[2] 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 = 3

**Output:** 5

**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

(https://leetcode.com/problems/allocate-mailboxes/)

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.

[3] 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 = 3

**Output:** 2

**Explanation:** Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

(https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/)

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.

[4] 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 = 1

**Output:** 3

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

(https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)

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

[5] 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 = 3

**Output: **2

**Explanation**: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

(https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/)

Approach — Use greedy approach. Compute the counts of each integer and using a min-heap, remove the integer with the current minimum count first.

[6] 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:** 2

**Explanation:** It could be decoded as "AB" (1 2) or "L" (12).

(https://leetcode.com/problems/decode-ways/)

Approach — Use recursion.

[7] 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".

(https://leetcode.com/problems/find-all-anagrams-in-a-string/)

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.

[8] 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.

**Note:**

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

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.

(https://leetcode.com/problems/word-ladder/)

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

[9] 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=6

**Output:** True

**Explanation:** Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

(https://leetcode.com/problems/continuous-subarray-sum/)

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.

[10] 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:** false

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

(https://leetcode.com/problems/course-schedule/)

Approach — Do DFS. If a cycle is found then return False else return True.

[11] 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, andn = 2.After removing the second node from the end, the linked list becomes1->2->3->5.

(https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

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.