This post is completed by 2 users

  • 0
 Add to List
Medium

456. Subsets Elements less than K.

Objective: Given an array of numbers and integer K. Your task is to find lengths of all the subsets which contain value K and all elements in the subset are less than equal to K.

Example:

Given Input: [1, 5, 2, 3, 8, 6, 2, 4, 9, 5, 2], and K = 5
Length of subsets(all elements <= k) which contains K: 6
Explanation:
subset {1, 5, 2, 3} , length=4
subset {5, 2} , length=2
Output: 2+4 = 6

Given Input: [1, 5, 2, 3, 8, 6, 2, 4, 9, 5, 2], and K = 9
Length of subsets(all elements <= k) which contains K: 11
All elements are less than 9 so array length is our result.

Naive Approach: Use nested loops, get all the subsets with all the elements less than k and pick the ones which contain value k and add their length to answer.

Time Complexity: O(N2)

Better Approach: 

  1. Initialize currentLength = 0, answer = 0, kPresent = false.
  2. Iterate through the input array.
    1. If current element is <= k
      1. Increment currentLength by 1.
      2. If current element == k, do kPresent = true.
    2. Else
      1. Check if kPresent = true then add currentLength to answer.
      2. Reset currentLength = 0, kPresent = false
  3. Handle the edge case, if kPresent = true then add currentLength to answer.
  4. Return the answer.

Time Complexity: O(N)

Output:

Given Input: [1, 5, 2, 3, 8, 6, 2, 4, 9, 5, 2], and K = 5
Length of subsets(all elements <= k) which contains K: 6

Related Problems: