Google Interview Question — LeetCode 1296

In this post, we are going to discuss leetcode 1296 — Divide Array in Sets of K Consecutive Numbers, which is recently asked in Google interviews.

Problem Analysis

Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.

Return true if it is possible. Otherwise, return false.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4 
Output: true 
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 
Output: true 
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

Input: nums = [1,2,3,4], k = 3 
Output: false 
Explanation: Each array should be divided in subarrays of size 3.

This is a math problem, and we will solve it with a count map.

My Thinking Process

We need to get sub-arrays of k consecutive numbers, and the first idea comes up into my mind is to use a count map.

We can formulate an approach to this problem by running over some examples. Let us say k is 3, and our smallest number in the array is 1. Then we can come up with the following scenarios:

1. We have n 1s, and m 2s, where m is smaller than n. In this case, we have to return False. Because for each 1, we cannot get a consecutive 2 for all of them.
2. We have n 1s, and m 2s, where m is larger than n. In this case, we can get a consecutive 2 for every 1. Then we have m-n 2s left. So for the left over 2s, we need to have m-n 3s to match with it. However, we also need n 3s to match with the 1s.

With the analysis above, the approach is becoming clear now. Basically, we need to do the following:

1. Build a count map for all the numbers.
2. Starting from the smallest number a, and loop from a to a+k, and we can do count[n]=count[n]-count[a], and it should be larger than or equal to 0.
3. Starting from the next non-zero number, and repeat step 2.
4. Keep looping, until we have the zero count for all the numbers.

Code Implementation

Base on the analysis above, below is my implementation of the problem.