Scale Engineer

Non-decreasing Subsequences

Med
#0478Time: O(n * 2^n). We iterate through `2^n` potential subsequences. For each, building the subsequence takes O(n) time, and validating it also takes O(n). Adding a list of size `k` to a hash set takes O(k) time. Thus, the overall complexity is dominated by this exponential factor.Space: O(n * 2^n). In the worst-case scenario (e.g., a sorted array of unique elements), the `resultSet` might need to store a number of subsequences on the order of `2^n`, with each subsequence having a length up to `n`.
Patterns
BacktrackingBit Manipulation
Data structures
ArrayHash Table

Prompt

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

 

Example 1:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

Example 2:

Input: nums = [4,4,3,2,1]
Output: [[4,4]]

 

Constraints:

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

Approaches

3 approaches with complexity analysis and trade-offs.

This approach generates every possible subsequence of the input array. Then, it filters these subsequences based on two criteria: they must be non-decreasing, and they must have a length of at least two. To handle duplicate subsequences that might be formed, a Set is used to store the valid ones, ensuring uniqueness.

Algorithm

  • Create a Set<List<Integer>> resultSet to store unique valid subsequences.
  • Get the length n of the input array nums.
  • Iterate through all possible non-empty subsets using a bitmask i from 1 to (1 << n) - 1.
  • For each bitmask i, construct the corresponding subsequence:
    • Create an empty List<Integer> subsequence.
    • Iterate from j = 0 to n - 1. If the j-th bit of i is set, add nums[j] to subsequence.
  • After constructing the subsequence, validate it:
    • If subsequence.size() < 2, discard it.
    • Check if the subsequence is non-decreasing. Iterate from the second element and ensure subsequence[k] >= subsequence[k-1].
    • If it is valid, add it to the resultSet.
  • Finally, convert the resultSet to a List and return it.

Walkthrough

The core of this method is to iterate through all 2^n subsets of the given array nums. We can achieve this using bit manipulation, where each integer from 1 to 2^n - 1 represents a bitmask. If the j-th bit in the mask is 1, it signifies that the j-th element of nums is included in the current subsequence.

For each generated subsequence, we perform two checks:

  1. Size Check: The subsequence must contain at least two elements.
  2. Non-decreasing Check: We iterate through the subsequence to ensure that each element is greater than or equal to the one preceding it.

If a subsequence satisfies both conditions, it is added to a Set<List<Integer>>. Using a Set conveniently handles the problem of duplicate subsequences, as a Set only stores unique elements. Finally, the contents of the Set are transferred to a List to match the required return type.

class Solution {    public List<List<Integer>> findSubsequences(int[] nums) {        Set<List<Integer>> resultSet = new HashSet<>();        int n = nums.length;        for (int i = 1; i < (1 << n); i++) {            List<Integer> subsequence = new ArrayList<>();            for (int j = 0; j < n; j++) {                if (((i >> j) & 1) == 1) {                    subsequence.add(nums[j]);                }            }            if (subsequence.size() >= 2) {                boolean isNonDecreasing = true;                for (int k = 1; k < subsequence.size(); k++) {                    if (subsequence.get(k) < subsequence.get(k - 1)) {                        isNonDecreasing = false;                        break;                    }                }                if (isNonDecreasing) {                    resultSet.add(subsequence);                }            }        }        return new ArrayList<>(resultSet);    }}

Complexity

Time

O(n * 2^n). We iterate through `2^n` potential subsequences. For each, building the subsequence takes O(n) time, and validating it also takes O(n). Adding a list of size `k` to a hash set takes O(k) time. Thus, the overall complexity is dominated by this exponential factor.

Space

O(n * 2^n). In the worst-case scenario (e.g., a sorted array of unique elements), the `resultSet` might need to store a number of subsequences on the order of `2^n`, with each subsequence having a length up to `n`.

Trade-offs

Pros

  • Conceptually simple and straightforward to implement.

  • Guaranteed to find all valid subsequences.

Cons

  • Extremely inefficient due to its O(n * 2^n) time complexity, making it unsuitable for n larger than about 20.

  • Generates a vast number of subsequences that are immediately discarded, wasting computation.

  • High space complexity to store all generated subsequences before filtering and then storing the results.

Solutions

class Solution {private  int[] nums;private  List<List<Integer>> ans;public  List<List<Integer>> findSubsequences(int[] nums) {    this.nums = nums;    ans = new ArrayList<>();    dfs(0, -1000, new ArrayList<>());    return ans;  }private  void dfs(int u, int last, List<Integer> t) {    if (u == nums.length) {      if (t.size() > 1) {        ans.add(new ArrayList<>(t));      }      return;    }    if (nums[u] >= last) {      t.add(nums[u]);      dfs(u + 1, nums[u], t);      t.remove(t.size() - 1);    }    if (nums[u] != last) {      dfs(u + 1, last, t);    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem