Coding Week 3 - Sorting and Prefix Sum Flashcards
Problem 1) Car Pooling (Sorting and Prefix Sum)
There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).
You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car’s initial location.
Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Constraints:
1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengersi <= 100
0 <= fromi < toi <= 1000
1 <= capacity <= 105
Question 1) What will be the asymptotic time and auxiliary space complexity of the most efficient approach, if the maximum value of ‘from’ and ‘to’ for any trip is 1000.
(N -> length of trips)
A) O(N), O(N)
B) O(N * log (N)), O(1)
C) O(N), O(1)
D) O(n ^ 2), O(1)
C) O(N), O(1)
Explanation: The most efficient approach for this problem is using bucket sort. The bucket sort is an O(N) sorting algorithm but requires some prior knowledge for the range of the data. So, if we know the range we can use bucket sort. Here, we know that the maximum value of ‘from’ and ‘to’ for any trip is 1000 so we will initiazel 1001 buckets, and put the number of passengers changed in corresponding buckets, and collect the buckets one by one.
We need to traverse the ‘trips’ once, hence time complexity will be O(N)
We need to store 1001 buckets, hence the auxiliary space complexity will be O(1).
Problem 1) Car Pooling
There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).
You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car’s initial location.
Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Constraints:
1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengersi <= 100
0 <= fromi < toi <= 1000
1 <= capacity <= 105
Question 2) In the sorting approach, we will need to the sorted values of:
A) ‘numPassengers’
B) ‘from’
C) ‘to’
D) ‘from’ and ‘to’.
D) ‘from’ and ‘to’.
Explanation: In sorting approach, we need the following information:
Timestamp when a passenger X gets into the car.
Timestamp when a passenger X gets out of the car.
A simple idea is to go through from the start to end, and check if the actual capacity exceeds capacity.
To know the actual capacity, we just need the number of passengers changed at each timestamp.
We can save the number of passengers changed at each time, sort it by timestamp, and finally iterate it to check the actual capacity.
Problem 2) Plates Between Candles (Prefix Sum)
There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters ‘’ and ‘|’ only, where a ‘’ represents a plate and a ‘|’ represents a candle.
You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti…righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.
For example, s = “|||||”, and a query [3, 8] denotes the substring “||**|”. The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.
Return an integer array answer where answer[i] is the answer to the ith query.
Example 1:
ex-1
Input: s = “||***|”, queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.
Example 2:
ex-2
Input: s = “|**||||**|*”, queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.
Constraints:
3 <= s.length <= 105
s consists of ‘*’ and ‘|’ characters.
1 <= queries.length <= 105
queries[i].length == 2
0 <= lefti <= righti < s.length
Question 1) There is a candle at index 3 and a candle at index 7 and the query is [3, 7] . Which of the following is the correct answer:
A) 3
B) 4
C) 1
D) Insufficient information
D) Insufficient information
Explanation: There is a possibility that there are other candles between index 3 to 7. So, the information provided in the question is not sufficient to answer this question.
Problem 2) Plates Between Candles (Prefix Sum)
There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters ‘’ and ‘|’ only, where a ‘’ represents a plate and a ‘|’ represents a candle.
You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti…righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.
For example, s = “|||||”, and a query [3, 8] denotes the substring “||**|”. The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.
Return an integer array answer where answer[i] is the answer to the ith query.
Example 1:
ex-1
Input: s = “||***|”, queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.
Example 2:
ex-2
Input: s = “|**||||**|*”, queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.
Constraints:
3 <= s.length <= 105
s consists of ‘*’ and ‘|’ characters.
1 <= queries.length <= 105
queries[i].length == 2
0 <= lefti <= righti < s.length
Question 2) What is the time and auxiliary space complexity of the prefix sum approach?
(N -> number of characters in s, Q -> number of queries).
A) Time - O(N * Q), Space - O(N)
B) Time - O(N * Q), Space - O(N ^ 2)
C) Time - O(N + Q), Space - O(N)
D) Time - O(N + Q), Space - O(Q)
C) Time - O(N + Q), Space - O(N)
Explanation:
We need to iterate the given string at most three times:
To find the prefix sum.
To find the nearest candle on the left for each index.
To find the nearest candle on the right for each index.
This will take O(3 * N) = O(N) time.
Answering Q queries will take O(Q) time. O(1) per query.
We will need three arrays of size N. Hence, The auxiliary space complexity will be O(3 * N) = O(N).
Problem 3) Maximum Units on a Truck (Sorting, Heap)
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
numberOfBoxesi is the number of boxes of type i.
numberOfUnitsPerBoxi is the number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.
Return the maximum total number of units that can be put on the truck.
Example 1:
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
Example 2:
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91
Constraints:
1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 106
Question 1) For the above problem, sorting approach is better than heap approach because:
A) Time complexity of the sorting approach is less than the heap approach.
B) Auxiliary space complexity of the sorting approach is less than the heap approach.
C) Heap approach doesn’t guarantee a right answer.
D) Both approaches are equally efficient.
B) Auxiliary space complexity of the sorting approach is less than the heap approach.
Explanation: In the heap approach, we need to maintain a heap which will take O(N) auxiliary space. In the sorting approach, we can sort the array in-place.
Problem 3) Maximum Units on a Truck (Sorting, Heap)
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
numberOfBoxesi is the number of boxes of type i.
numberOfUnitsPerBoxi is the number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.
Return the maximum total number of units that can be put on the truck.
Example 1:
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
Example 2:
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91
Constraints:
1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 106
Question 2) The efficient approach of solving this problem has the time and auxiliary space complexity of:
(N -> length of ‘boxTypes’ array)
A) Time - O(N), Space - O(N)
B) Time - O(N * log (N)), Space - O(N)
C) Time - O(N * log (N)), Space - O(1)
D) Time - O(N ^ 2), Space - O(N)
C) Time - O(N * log (N)), Space - O(1)
Explanation: The simple way to implement this is to sort the array boxTypes in decreasing order of a number of units. Once all the elements in array boxTypes are sorted in that order, we know that box type at the 0th position is the one with maximum units and the one at 1st position having the second highest number of units and so on.
The sorting takes O(N * log (N)) time and we will require only a constant amount of extra space.
Problem 4) Reorganize String (Sorting, Heap, Hashtable)
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return “” if not possible.
Example 1:
Input: s = “aab”
Output: “aba”
Example 2:
Input: s = “aaab”
Output: “”
Constraints:
1 <= s.length <= 500
s consists of lowercase English letters.
Question 1) Can we solve this problem without sorting?
A) Yes
B) No
A) Yes
Explanation: We only need to find the character with maximum frequency.
Calculate the frequencies of every character in the input string
If a character with a maximum frequency has a frequency greater than (n + 1) / 2, then return an empty string, as it is not possible to construct a string
Now fill the even index positions with the maximum frequency character, if some even positions are remaining then first fill them with remaining characters
Then fill odd index positions with the remaining characters
Return the constructed string
Problem 4) Reorganize String (Sorting, Heap, Hashtable)
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return “” if not possible.
Example 1:
Input: s = “aab”
Output: “aba”
Example 2:
Input: s = “aaab”
Output: “”
Constraints:
1 <= s.length <= 500
s consists of lowercase English letters.
Question 2) What will be the time and auxiliary space complexity of the most efficient approach to solve the above problem?
A) O(N), O(1)
B) O(N * log (N)), O(N)
C) O(N), O(1)
D) O(N ^ 2), O(N)
C) O(N), O(1)
Explanation: We need to find the frequency of each character which will take O(N) time.
We need to store a frequency of only 26 characters in the worst case. Hence, the auxiliary space complexity will be O(1).
Least Number of Unique Integers after K Removals (Sorting, Heap)
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.
Example 1:
Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
Example 2:
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.
Constraints:
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length
Question 1) What will be the asymptotic time and auxiliary space complexity of the (HashTable + Heap) approach
(N -> length of arr)
A) O(N * log (N)), O(N)
B) O(N), O(N)
C) O(K), O(1)
D) O(N * log (K)), O(N)
A) O(N * log (N)), O(N)
Explanation: We need to find the frequency of each integer and sort them.
Sorting frequencies will take O(N * log (N)) time.
Storing frequencies will take O(N) extra space.
Least Number of Unique Integers after K Removals (Sorting, Heap)
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.
Example 1:
Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
Example 2:
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.
Constraints:
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length
Question 2) Can you solve this problem in O(N) time, if you know the range of the integers?
(N -> length of arr)
A) Yes
B) No
A) Yes
Explanation: We can use bucket sort to solve this problem in O(N) time if we know the range of the integers.
