Last updated on February 20th, 2025 at 09:50 am

Here, we see a Non-decreasing Subsequences LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth First Search

Companies

Yahoo

Level of Question

Medium

Non-decreasing Subsequences LeetCode Solution

1. Problem Statement

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]]

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Subsets (Backtracking)”. The problem involves generating all possible subsequences of an array that satisfy a specific condition (non-decreasing order). This is a classic example of the Subsets pattern, where we explore all possible combinations of elements using recursion and backtracking.

3. Code Implementation in Different Languages

3.1 Non-decreasing Subsequences C++

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int>temp;
        set<vector<int>>ans;
        func(0,nums,temp,ans);
        return vector(ans.begin(),ans.end());
    }
    void func(int idx,vector<int>&nums,vector<int>&a,set<vector<int>>&ans){
        int n=nums.size();
        if(idx>=n){
            if(a.size()>=2){
                ans.insert(a);
            }
            return ;
        }
        if(!a.size()||nums[idx]>=a.back()){
            a.push_back(nums[idx]);
            func(idx+1,nums,a,ans);
            a.pop_back();
        }
        func(idx+1,nums,a,ans); 
    }
};

3.2 Non-decreasing Subsequences Java

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> ans = new HashSet<>();
        solve(nums, 0, new ArrayList<>(), ans);
        return new ArrayList<>(ans);
    }
    public void solve(int[] nums, int index, List<Integer> output, Set<List<Integer>> ans) {
        if (index >= nums.length) {
            if (output.size() > 1) {
                ans.add(new ArrayList<>(output));
            }
            return;
        }
        if (output.isEmpty() || nums[index] >= output.get(output.size() - 1)) {
            output.add(nums[index]);
            solve(nums, index+1, output, ans);
            output.remove(output.size() - 1);
        }
        solve(nums, index+1, output, ans);
    }
}

3.3 Non-decreasing Subsequences JavaScript

var findSubsequences = function(nums) {
    let res = []
    let map = {}
    let iterate = (index,temp) =>{
        if(map[temp]) return;
        if(temp.length>=2){
            res.push(temp)
        }
        for(let i =index;i<nums.length;i++){
            if(temp[temp.length-1]>nums[i]) continue;
            map[temp] = true;
            iterate(i+1,[...temp,nums[i]])
        }
    }
    iterate(0,[])
    return res;
};

3.4 Non-decreasing Subsequences Python

class Solution(object):
    def findSubsequences(self, nums):
        ans = set()
        self.solve(nums, 0, [], ans)
        return [list(x) for x in ans]
    def solve(self, nums, index, output, ans):
        if index >= len(nums):
            if len(output) > 1:
                ans.add(tuple(output))
            return
        if not output or nums[index] >= output[-1]:
            output.append(nums[index])
            self.solve(nums, index+1, output, ans)
            output.pop()
        self.solve(nums, index+1, output, ans)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(2n * n)	O(n * 2n)
Java	O(2n * n)	O(n * 2n)
JavaScript	O(2n * n)	O(n * 2n)
Python	O(2n * n)	O(n * 2n)

Time Complexity:

• Subset Generation: The recursion explores all possible subsets of the input array. For an array of size n, there are 2n subsets.
• Validation and Copying: For each subset, we check if it is valid (non-decreasing and size >= 2). Copying a subset into the result set or list takes O(n) time in the worst case.
• Overall Time Complexity: O(2ⁿ * n).

Space Complexity:

• Recursion Stack: The recursion depth is at most n (the size of the input array), so the recursion stack uses O(n) space.
• Result Storage: The result set or list stores all valid subsets. In the worst case, there can be O(2ⁿ) subsets, and each subset can have up to n elements. Thus, the space required for storing subsets is O(n * 2ⁿ).
• Overall Space Complexity: O(n * 2ⁿ).

• The use of a set (C++, Java, Python) or a map (JavaScript) ensures that duplicate subsequences are not added to the result.
• Backtracking is used to explore all possible combinations efficiently by adding and removing elements from the current subsequence.
• The algorithm is exponential in nature due to the subset generation process, which is unavoidable for this type of problem.