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.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Bit Manipulation, Backtracking
- Asked at: Amazon, Yahoo
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
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.
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.
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
dfs(pos, path): ifpathhas at least two elements, record a copy.- Scan
ifrompos + 1to the end; for eachnums[i]that is at least the last value ofpath(or any value whenpathis empty), remember its first such index. - For each remembered value in increasing order, append it, recurse with
posset to its first index, and remove it. - 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 outJava
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