Non-decreasing Subsequences

MEDIUM

Description

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

Checkout 3 different approaches to solve Non-decreasing Subsequences. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Generate and Filter

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.

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:

Size Check: The subsequence must contain at least two elements.
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 Analysis

Time Complexity: 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 Complexity: 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`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Non-decreasing Subsequences. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Non-decreasing Subsequences

Patterns:

BacktrackingBit Manipulation

Data Structures:

ArrayHash Table