Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1121. Divide Array Into Increasing Sequences - Leetcode Solution

Code Implementation

from collections import Counter, defaultdict

class Solution:
    def canDivideIntoSubsequences(self, nums, k):
        # Find the maximum frequency of any number
        freq = Counter(nums)
        max_freq = max(freq.values())
        # The answer is whether len(nums) >= max_freq * k
        return len(nums) >= max_freq * k
      
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool canDivideIntoSubsequences(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        int max_freq = 0;
        for (int num : nums) {
            freq[num]++;
            max_freq = max(max_freq, freq[num]);
        }
        return nums.size() >= max_freq * k;
    }
};
      
import java.util.*;

class Solution {
    public boolean canDivideIntoSubsequences(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        int maxFreq = 0;
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
            maxFreq = Math.max(maxFreq, freq.get(num));
        }
        return nums.length >= maxFreq * k;
    }
}
      
var canDivideIntoSubsequences = function(nums, k) {
    let freq = {};
    let maxFreq = 0;
    for (let num of nums) {
        freq[num] = (freq[num] || 0) + 1;
        maxFreq = Math.max(maxFreq, freq[num]);
    }
    return nums.length >= maxFreq * k;
};

Problem Description

You are given a non-decreasing array nums and an integer k. Your task is to determine whether it is possible to split nums into one or more subsequences such that:
  • Each subsequence is strictly increasing (i.e., each element is greater than the previous).
  • Each element from nums is used exactly once (no element is reused).
  • Each subsequence has at least k elements.
There is guaranteed to be at least one valid solution if possible. The function should return True if it's possible to split nums as described, or False otherwise.

Thought Process

At first glance, you might consider brute-forcing all possible subsequence splits, but that quickly becomes infeasible for large arrays. Instead, let's think about the constraints:
  • Because nums is non-decreasing, repeated numbers can't be in the same strictly increasing subsequence.
  • The number that appears most frequently in nums (let's call this frequency max_freq) determines the minimum number of subsequences we must create — each occurrence must go into a different subsequence to maintain strictly increasing order.
  • Each subsequence must have at least k elements, so we need at least max_freq * k elements in total to satisfy all subsequences.
This leads to an optimized check: Is the length of nums at least max_freq * k? If yes, it's possible; if not, it's impossible.

Solution Approach

Let's break down the steps:
  1. Count the Frequency: Use a hash map (dictionary) to count how many times each number appears in nums. This helps us find max_freq, the maximum frequency of any number.
  2. Calculate the Minimum Required Length: Since each occurrence of the most frequent number needs its own subsequence, and each subsequence needs at least k elements, we must have at least max_freq * k elements in total.
  3. Final Check: If the length of nums is greater than or equal to max_freq * k, return True; otherwise, return False.

We use a hash map (dictionary) for counting because it offers fast, O(1) lookups and updates, making our solution efficient even for large arrays.

Example Walkthrough

Suppose nums = [1,2,2,3,3,4,4,5] and k = 3.

  1. Count the frequency of each number:
    • 1: 1 time
    • 2: 2 times
    • 3: 2 times
    • 4: 2 times
    • 5: 1 time
    So max_freq = 2.
  2. Calculate minimum required elements: 2 * 3 = 6.
  3. Check if len(nums) = 8 is at least 6. It is, so the answer is True.
  4. How would the split look? One possible way is:
    • Subsequence 1: 1,2,3,4
    • Subsequence 2: 2,3,4,5
    Each is strictly increasing and has at least 3 elements.

Time and Space Complexity

  • Brute-force approach: Trying all possible splits is exponential in time — O(2^n) — and not feasible for large input.
  • Optimized approach (current solution):
    • Time Complexity: O(n), where n is the length of nums, since we only need one pass to count frequencies.
    • Space Complexity: O(n) in the worst case (if all numbers are unique), due to the frequency map.

Summary

The key insight is that the most frequent number in nums determines the minimum number of subsequences needed, and each must have at least k elements. By checking if the array is large enough to accommodate max_freq subsequences of length k, we can solve the problem efficiently. This approach avoids brute-force and leverages counting for a clean, O(n) solution.