We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Non-decreasing Subsequences

Number: 491

Difficulty: Medium

Paid? No

Companies: Amazon, Yahoo

Problem Description

Given an integer array, return all the different possible non-decreasing subsequences of the given array with at least two elements. A subsequence is formed by deleting some or no elements without changing the order of the remaining elements.

Key Insights

  • Use backtracking (depth-first search) to explore all possible subsequences.
  • At each recursive call, ensure the current subsequence is non-decreasing by comparing the last element of the subsequence with the current element.
  • Use a local hash set at each level of recursion to avoid duplicate subsequences from the same recursive level.
  • Since array length is relatively small (maximum 15), a DFS exploring 2^n possibilities is feasible.

Space and Time Complexity

Time Complexity: O(2^n) in the worst-case scenario as all combinations might be explored. Space Complexity: O(n) recursion depth plus additional space to store the resulting subsequences.

Solution

We solve the problem using a backtracking approach. The algorithm recursively builds subsequences by iterating through the array from a given start index. At each step:

  1. If the current subsequence is non-empty and meets the non-decreasing condition (i.e., either it is empty or the last element is less than or equal to the current element), add the element and continue the recursion.
  2. When the subsequence length is at least two, record the current subsequence in our result.
  3. To avoid duplicates within the same recursion depth, use a set to store the elements that have been used at the current recursive call.
  4. Backtrack to explore other possible subsequences.

This approach guarantees that all valid non-decreasing subsequences are captured while avoiding duplicate work.

Code Solutions

# Function to find all non-decreasing subsequences
def findSubsequences(nums):
    # List to store the final valid subsequences
    result = []

    # Recursive helper function for backtracking
    def backtrack(start, current):
        # If current subsequence has at least two numbers, add a copy to the result
        if len(current) >= 2:
            result.append(current[:])
        
        # Set to track elements used at this recursion level to avoid duplicates
        used = set()
        # Loop over the remaining elements starting from 'start'
        for i in range(start, len(nums)):
            # If current is empty or the last element is less than or equal to nums[i]
            # and if nums[i] has not already been used at this recursion level
            if (not current or current[-1] <= nums[i]) and nums[i] not in used:
                used.add(nums[i])
                current.append(nums[i])
                backtrack(i + 1, current)
                current.pop()  # Backtrack

    backtrack(0, [])
    return result

# Example Usage
nums = [4, 6, 7, 7]
print(findSubsequences(nums))
← Back to All Questions