Coding Week 2 - Arrays Flashcards
1) Pairs of Songs With Total Durations Divisible by 60
You are given a list of songs where the ith song has a duration of time[i]seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j, with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Question 1) Can you reduce this problem to two sum problem?
A) Yes
B) No
A) Yes.
Explanation:
For any valid pair (a, b), the following condition should be true:
=> (a + b) % 60 = 0
=> ((a % 60) + (b % 60)) % 60 = 0
=> ((a % 60) + (b % 60)) = 0 or ((a % 60) + (b % 60)) = 60
We can just replace time[i] with (time[i] % 60) and then, we just need to find the pair of numbers whose sum is either 60 or 0.
1) Pairs of Songs With Total Durations Divisible by 60
You are given a list of songs where the ith song has a duration of time[i]seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j, with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Question 2) What is the time and space complexity of the most efficient approach?
(N -> Length of ‘time’ array)
A) Time - O(N), Space - O(N)
B) Time - O(N ^ 2), Space - O(N)
C) Time - O(N), Space - O(1)
D) Time - O(N * log(N)), Space - O(1)
C) Time - O(N), Space - O(1)
Explanation:
To solve this problem, we can store the frequencies of the remainder (a % 60), so that we can find the number of the complements in O(1). We would initiate an array ‘remainder’ with size 60 to record the frequencies of each remainder - as the range of remainders is [0,59]. Then we can loop through the array once and for each element a we would:
a % 60 = 0 add remainders[0] to the result, else, add remainders[60 - a % 60] to the result.
Increment [a % 60] by 1.
We are iterating through each element only once. Hence, time complexity will be O(N)
We are using an array of fixed length. Hence, space complexity will be O(1).
2) Most Common Word
Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.
The words in the paragraph are case-insensitive and the answer should be returned in lowercase.
Example 1:
Input: paragraph = “Bob hit a ball, the hit BALL flew far after it was hit.”, banned = [“hit”]
Output: “ball”
Explanation:
“hit” occurs 3 times, but it is a banned word.
“ball” occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph.
Question 1) What is the time and space complexity of the Hash Table approach?
(N -> Number of characters in the input string and M -> Number of characters in the banned list)
A) Time - O(N + M), Space - O(1)
B) Time - O(N + M), Space - O(N + M)
C) Time - O(N * M), Space - O(N + M)
D) Time - O(N ^ 2), Space - O(M)
B) Time - O(N + M), Space - O(N + M)
We built a hash table to count the frequency of each unique word, in O(N) time. Similarly, we built a set out of the banned word list, which would take additional O(M) time. Hence time complexity will be O(N + M).
The Hash table will consume O(N) space and the set will consume O(M) space. Hence, the space complexity will be O(N + M).
3) Shortest Unsorted Continuous Subarray
Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.
Return the shortest such subarray and output its length.
Example 1:
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Question 1) Suppose the Shortest Unsorted Continuous Subarray is from index ‘start’ to ‘end’, then which of the following conditions are ALWAYS true:
A) All the elements from 0 to ‘start’-1, are less than nums[‘start’].
B) All the elements from ‘end’+1 to n-1 are greater than nums[‘end’].
C) nums[‘start’] is the maximum element
D) nums[‘end’] is the minimum element
A) All the elements from 0 to ‘start’-1, are less than nums[‘start’].
B) All the elements from ‘end’+1 to n-1 are greater than nums[‘end’].
(For a sorted(increasing order) array, if we plot the elements on a graph the curve will always be moving up from left to right and moving down from right to left).
The ‘start’ index is the last index from the right for which the direction of the slope changes(the down going curve moves up).
The ‘end’ index is the last index from the left for which the direction of the slope changes(the upgoing curve moves down).
3) Shortest Unsorted Continuous Subarray
Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.
Return the shortest such subarray and output its length.
Example 1:
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Question 2) What will be the time complexity of the most efficient approach?
(N -> length of ‘nums’)
A) Time - O(N), Space - O(1)
B) Time - O(N), Space - O(N)
C) Time - O(N ^ 2), Space - O(N)
D) Time - O(N ^ 2), Space - O(1)
A) Time - O(N), Space - O(1)
We will traverse the ‘nums’ array once from left to right and once from right to left to find the changes in the slope. Hence the time complexity will be O(N) + O(N), which is asymptotically O(N).
We will use only a constant amount of extra space. Hence, space complexity will be O(1).
4) String Compression
Given an array of characters chars, compress it using the following algorithm:
Begin with an empty string s. For each group of consecutive repeating characters in chars:
If the group’s length is 1, append the character to s.
Otherwise, append the character followed by the group’s length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.
After you are done modifying the input array, return the new length of the array.
You must write an algorithm that uses only constant extra space.
Example 1:
Input: chars = [“a”,”a”,”b”,”b”,”c”,”c”,”c”]
Output: Return 6, and the first 6 characters of the input array should be: [“a”,”2”,”b”,”2”,”c”,”3”]
Explanation: The groups are “aa”, “bb”, and “ccc”. This compresses to “a2b2c3”.
Question 1) In the two pointers approach, what are the initial indexes of ‘p1’ and ‘p2’ pointers?
(N -> length of ‘chars’ array)
A) p1 -> 0, p2 -> N - 1
B) p1 -> 0, p2 -> 0
C) p1 -> N/2, p2 -> N - 1
D) p1 -> 0, p2 -> N/2
B) p1 -> 0, p2 -> 0
The idea is to set p1 and p2 at the index 0 and move the pointer p2 until (chars[p1] == chars[p2]). If (chars[p1] != chars[p2]), set p1 = p2.
4) String Compression
Given an array of characters chars, compress it using the following algorithm:
Begin with an empty string s. For each group of consecutive repeating characters in chars:
If the group’s length is 1, append the character to s.
Otherwise, append the character followed by the group’s length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.
After you are done modifying the input array, return the new length of the array.
You must write an algorithm that uses only constant extra space.
Example 1:
Input: chars = [“a”,”a”,”b”,”b”,”c”,”c”,”c”]
Output: Return 6, and the first 6 characters of the input array should be: [“a”,”2”,”b”,”2”,”c”,”3”]
Explanation: The groups are “aa”, “bb”, and “ccc”. This compresses to “a2b2c3”.
Q2. What will the time and space complexity of two pointers approach?
(N -> length of ‘chars’ array)
A) Time - O(N), Space - O(1)
B) Time - O(N), Space - O(N)
C) Time - O(N ^ 2), Space - O(1)
D) Time - O(N ^ 2), Space - O(N)
A) Time - O(N), Space - O(1)
We will traverse each character of the ‘chars’ array at most twice. Hence, the time complexity will be O(N).
We will use only a constant amount of extra space. Hence, the space complexity will be O(1).
