LeetCode 1121. Divide Array Into Increasing Sequences Solution in Java, C++, Python & Go | Explanation + Code

Description

Given an integer array nums sorted in non-decreasing order and an integer k, return true if this array can be divided into one or more disjoint increasing subsequences of length at least k, or false otherwise.

 

Example 1:

Input: nums = [1,2,2,3,3,4,4], k = 3
Output: true
Explanation: The array can be divided into two subsequences [1,2,3,4] and [2,3,4] with lengths at least 3 each.

Example 2:

Input: nums = [5,6,6,7,8], k = 3
Output: false
Explanation: There is no way to divide the array using the conditions required.

 

Constraints:

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105
• nums is sorted in non-decreasing order.

Solutions

Solution 1: Quick Thinking

We assume that the array can be divided into m strictly increasing subsequences of length at least k. If the number of the most frequent number in the array is cnt, then these cnt numbers must be in different subsequences, so m ≥ cnt. Also, since the length of m subsequences is at least k, the fewer the number of subsequences, the better, so m = cnt. Therefore, cnt × k ≤ n must be satisfied. Hence, we only need to count the number of the most frequent number cnt in the array, and then judge whether cnt × k ≤ n. If it is, return true, otherwise return false.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array nums.

PythonJavaC++Go

class Solution: def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool: mx = max(len(list(x)) for _, x in groupby(nums)) return mx * k <= len(nums)(code-box)

class Solution { public boolean canDivideIntoSubsequences(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); int mx = 0; for (int x : nums) { mx = Math.max(mx, cnt.merge(x, 1, Integer::sum)); } return mx * k <= nums.length; } }(code-box)

class Solution { public: bool canDivideIntoSubsequences(vector<int>& nums, int k) { int cnt = 0; int a = 0; for (int& b : nums) { cnt = a == b ? cnt + 1 : 1; if (cnt * k > nums.size()) { return false; } a = b; } return true; } };(code-box)

func canDivideIntoSubsequences(nums []int, k int) bool { cnt, a := 0, 0 for _, b := range nums { cnt++ if a != b { cnt = 1 } if cnt*k > len(nums) { return false } a = b } return true }(code-box)

Solution 2

Java

class Solution { public boolean canDivideIntoSubsequences(int[] nums, int k) { int cnt = 0; int a = 0; for (int b : nums) { cnt = a == b ? cnt + 1 : 1; if (cnt * k > nums.length) { return false; } a = b; } return true; } }(code-box)