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

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

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:

1. Only one letter can be changed at a time.
2. 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: 5
Explanation: 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, and n = 2.
After removing the second node from the end, the linked list becomes 1->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.