Divide Array into Increasing Sequences in Python

Suppose we have a non-decreasing array of positive integers called nums and an integer K, we have to find out if this array can be divided into one or more number of disjoint increasing subsequences of length at least K.

So, if the input is like nums = [1,2,2,3,3,4,4], K = 3, then the output will be true, as this array can be divided into the two subsequences like [1,2,3,4] and [2,3,4] with lengths at least 3 each.

To solve this, we will follow these steps −

• d := a new map

• req := 0

• for each i in nums, do

  • if i not in d is non-zero, then

    • d[i]:= 1

  • otherwise,

    • d[i] := d[i] + 1

  • req := maximum of req, d[i]

• return true when req*K <= size of nums

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution(object):
   def canDivideIntoSubsequences(self, nums, K):
      d = {}
      req = 0
      for i in nums:
         if i not in d:
            d[i]=1
         else:
            d[i]+=1
            req = max(req,d[i])
      return req*K<=len(nums)
ob = Solution()
print(ob.canDivideIntoSubsequences([1,2,2,3,3,4,4],3))

Input

[1,2,2,3,3,4,4]. 3

Output

True