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…