Non-decreasing Subsequences

Medium
1592.

Non-decreasing Subsequences

Non-decreasing Subsequences is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon and Yahoo interviews.

Return every distinct subsequence of nums that has at least two elements and is non-decreasing (each element is at least the one before it). A subsequence keeps the original order but may skip elements; two subsequences that read the same value by value count once, even if they come from different positions.

List the subsequences in lexicographic order: compare value by value from the left; when one is a prefix of the other, the shorter comes first.

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

Example 3

Input
nums = [3,-1,3,0]
Output
[[-1,0],[-1,3],[3,3]]

Constraints

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Non-decreasing Subsequences — Solution in Python, Java & C++

Non-decreasing Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Non-decreasing Subsequences is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon and Yahoo interviews.

Problem statement

Return every distinct subsequence of nums that has at least two elements and is non-decreasing (each element is at least the one before it). A subsequence keeps the original order but may skip elements; two subsequences that read the same value by value count once, even if they come from different positions.

List the subsequences in lexicographic order: compare value by value from the left; when one is a prefix of the other, the shorter comes first.

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

Example 3

Input: nums = [3,-1,3,0]
Output: [[-1,0],[-1,3],[3,3]]

Constraints

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

Hints for Non-decreasing Subsequences

  1. Hint 1

    Build subsequences by choosing the index of the next element, which must be later in the array and not smaller than the last chosen value.

  2. Hint 2

    Duplicates appear when the same value is chosen at the same step from different positions. At each step, use each value at most once — its earliest remaining occurrence is always the best choice, because it leaves the most room afterwards.

  3. Hint 3

    If, at each step, you try the candidate values in increasing order and record a subsequence before extending it, the results come out in lexicographic order with no sorting.

How to solve Non-decreasing Subsequences

Generate each distinct value sequence through its earliest-possible embedding: at every step choose a value (not an index), and take that value's first occurrence after the current position. Distinct choices give distinct sequences, so no hash set of results is needed.

Approach

  1. dfs(pos, path): if path has at least two elements, record a copy.
  2. Scan i from pos + 1 to the end; for each nums[i] that is at least the last value of path (or any value when path is empty), remember its first such index.
  3. For each remembered value in increasing order, append it, recurse with pos set to its first index, and remove it.
  4. Start with dfs(-1, []).

Why it works

Any non-decreasing value sequence that occurs in nums also occurs when every element is matched as early as possible, and that greedy embedding is unique — so each distinct subsequence is produced exactly once. Recording before extending puts a prefix before its extensions, and increasing candidate order at every depth makes the whole output lexicographic.

Complexity

  • Time — O(2^n · n) in the worst case
  • Space — O(n) recursion depth besides the output

Pitfalls

  • Deduplicate per recursion level (or globally with a set); deduplicating only adjacent equal elements is wrong because the array is not sorted.
  • Do not sort nums — the order of the original array defines which subsequences exist.
  • Single elements are not answers; record only paths of length ≥ 2.

Reference solution

Python

from typing import List

def findSubsequences(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    out = []
    path = []

    def dfs(pos):
        if len(path) >= 2:
            out.append(path[:])
        first = {}
        for i in range(pos + 1, n):
            if path and nums[i] < path[-1]:
                continue
            if nums[i] not in first:
                first[nums[i]] = i
        for v in sorted(first):
            path.append(v)
            dfs(first[v])
            path.pop()

    dfs(-1)
    return out

Java

public static int[][] findSubsequences(int[] nums) {
    List<int[]> out = new ArrayList<>();
    subseqDfs(nums, -1, new int[nums.length], 0, out);
    return out.toArray(new int[0][]);
}

static void subseqDfs(int[] nums, int pos, int[] path, int len, List<int[]> out) {
    if (len >= 2) out.add(Arrays.copyOf(path, len));
    TreeMap<Integer, Integer> first = new TreeMap<>();
    for (int i = pos + 1; i < nums.length; i++) {
        if (len > 0 && nums[i] < path[len - 1]) continue;
        first.putIfAbsent(nums[i], i);
    }
    for (Map.Entry<Integer, Integer> e : first.entrySet()) {
        path[len] = e.getKey();
        subseqDfs(nums, e.getValue(), path, len + 1, out);
    }
}

C++

void subseqDfs(vector<int>& nums, int pos, vector<int>& path, vector<vector<int>>& out) {
    if (path.size() >= 2) out.push_back(path);
    map<int, int> first;
    for (int i = pos + 1; i < (int)nums.size(); i++) {
        if (!path.empty() && nums[i] < path.back()) continue;
        first.emplace(nums[i], i);
    }
    for (auto& e : first) {
        path.push_back(e.first);
        subseqDfs(nums, e.second, path, out);
        path.pop_back();
    }
}

vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<vector<int>> out;
    vector<int> path;
    subseqDfs(nums, -1, path, out);
    return out;
}

JavaScript

var findSubsequences = function(nums) {
    var n = nums.length;
    var out = [];
    var path = [];
    var dfs = function(pos) {
        if (path.length >= 2) out.push(path.slice());
        var first = new Map();
        for (var i = pos + 1; i < n; i++) {
            if (path.length && nums[i] < path[path.length - 1]) continue;
            if (!first.has(nums[i])) first.set(nums[i], i);
        }
        var vals = Array.from(first.keys()).sort(function(a, b) { return a - b; });
        for (var t = 0; t < vals.length; t++) {
            path.push(vals[t]);
            dfs(first.get(vals[t]));
            path.pop();
        }
    };
    dfs(-1);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets