Unique Integer Sequences — Problem Statement & Solution Guide
Problem Description
Given an array of integers arr and an integer k, identify all unique sequences of length k that can be constructed by selecting elements from arr. A valid sequence must consist of distinct integers, meaning no integer value may appear more than once within a single sequence. The order of elements in the sequence matters, so [1, 2] and [2, 1] are considered different sequences if both are valid.
Your task is to return a list of all such unique sequences. To ensure efficiency with large inputs, the solution must avoid generating duplicate sequences that arise from duplicate values in the input array. For instance, if the input contains multiple instances of the number 5, sequences using 5 should only be generated once per unique combination of other elements, not once for each occurrence of 5 in the array.
The output should be a list of lists, where each inner list represents a valid unique sequence of length k. If no such sequences exist (e.g., if k is greater than the number of distinct integers in arr), return an empty list.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Integer Sequences"
WHY DOES IT MATTER?
Generating permutations efficiently is a cornerstone of many algorithmic challenges, from combinatorial enumeration to scheduling and cryptographic key generation. Mastering the two‑pointer swapping technique equips engineers to write concise, memory‑efficient code that scales with input size.
OPTIMIZATION CHALLENGE
The key insight is that by swapping the current element with each candidate and recursing on the subarray, we avoid maintaining a separate visited set and automatically enforce uniqueness. This reduces both time (by pruning duplicate work) and space (by reusing the input array).
REAL-WORLD CONNECTION
Think of a distributed system that needs to assign k distinct tasks to k workers from a pool of n available tasks. The system must consider every possible ordered assignment to evaluate load balancing. Using the two‑pointer permutation algorithm is analogous to generating all possible task assignments without redundant bookkeeping.
When presenting this solution in an interview, emphasize that the algorithm’s core is a simple loop over the remaining elements and a single swap operation. Highlight that the recursion depth equals k, so the stack usage is predictable and small.
COMPLEXITY AT A GLANCE
O(P(n_unique,k)) where P(n,k)=n!/(n-k)!O(k) for recursion stack plus outputCore Theory — Why This Approach?
The problem asks for all length‑k sequences that can be built from an array of integers where each sequence contains distinct values and order matters. A naive approach would enumerate every possible k‑tuple from the array, which is O(n^k) time and would generate many duplicate sequences when the array contains repeated values. This brute force method quickly becomes infeasible as n grows, especially when n is large and k is close to n.
The optimal paradigm treats the array as a multiset of unique values. First, deduplicate the input to obtain a list of distinct integers. Then, generate all k‑length permutations of this list. This can be done efficiently with backtracking and in‑place swapping, a classic two‑pointer technique where one pointer marks the current position and the other iterates over candidates to swap into that position. By marking elements as used via swapping, we avoid extra memory for a visited set and guarantee that each recursive call works on a smaller subproblem.
Because the number of valid sequences equals the number of k‑permutations of n distinct elements, P(n,k)=n!/(n-k)!, the algorithm’s time complexity is proportional to this value. The space overhead is limited to the recursion stack and the output list, yielding O(k) auxiliary space. This approach scales far better than the exponential blow‑up of the brute force method and is the standard solution for permutation generation problems.
Interview Questions on This Problem
Q1How would you modify the algorithm if the input array could contain negative numbers and you only want sequences where the sum of elements is even?
After generating each k‑length permutation, compute its sum and check parity. To avoid generating all permutations, you can prune branches early: keep a running sum modulo 2 during backtracking and only continue if the remaining positions can potentially lead to an even sum. This reduces unnecessary exploration and keeps the algorithm efficient.
Q2A fintech company asks: "What is the time complexity of generating all unique k‑length sequences from an array of size n with possible duplicates?"
First deduplicate the array to get n_unique distinct values. The number of sequences is P(n_unique,k)=n_unique!/(n_unique-k)!. Therefore, the time complexity is O(P(n_unique,k)). If n_unique≈n, it simplifies to O(n!/(n-k)!).
Q3During a coding interview, you’re asked to explain why backtracking with swapping is preferable over using a visited boolean array for this problem. What would you say?
Swapping in place eliminates the need for an auxiliary visited array, reducing memory usage to O(1) beyond the recursion stack. It also guarantees that each recursive call works on a contiguous segment of the array, which can improve cache locality and simplify the code by avoiding extra data structures.
Examples
Input
arr = [1, 2, 3], k = 2
Output
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
Explanation: The array contains three distinct integers: 1, 2, and 3. We need to form sequences of length 2 with distinct elements. The possible permutations of choosing 2 elements from 3 are: (1,2), (1,3), (2,1), (2,3), (3,1), (3,2). Since all elements are unique in the input, all these permutations are valid and unique.
Input
arr = [1, 1, 2], k = 2
Output
[[1, 2], [2, 1]]
Explanation: The distinct integers in the array are {1, 2}. We need sequences of length 2 with distinct elements. The possible permutations are (1, 2) and (2, 1). Although there are two 1s in the input, the sequence [1, 2] is generated only once because the value 1 is treated as a single distinct entity for the purpose of uniqueness. The sequence [1, 1] is invalid because the elements must be distinct.
Input
arr = [4, 5, 6, 4], k = 3
Output
[[4, 5, 6], [4, 6, 5], [5, 4, 6], [5, 6, 4], [6, 4, 5], [6, 5, 4]]
Explanation: The distinct integers are {4, 5, 6}. We need sequences of length 3 with distinct elements. This is equivalent to finding all permutations of the set {4, 5, 6}. There are 3! = 6 such permutations. The duplicate 4 in the input does not create additional unique sequences because the value 4 is already accounted for in the distinct set.
Input
arr = [7, 7, 7], k = 2
Output
[]
Explanation: The distinct integers in the array are {7}. We need sequences of length 2 with distinct elements. However, there is only one distinct integer available. It is impossible to form a sequence of length 2 with distinct elements using only the value 7. Therefore, the result is an empty list.
Constraints
- 1 <= arr.length <= 10^5
- -10^9 <= arr[i] <= 10^9
- 1 <= k <= 10
- The number of distinct integers in arr is at most 1000
- The total number of unique sequences will not exceed 10^5
Optimal Approach & Strategy
Deduplicate the array to n_unique values, then use backtracking with in‑place swapping to generate all k‑length permutations. The algorithm runs in O(P(n_unique,k)) time and uses O(k) auxiliary space.
Brute Force Approach
Generate all n^k possible k‑tuples from the array, then filter out those that contain duplicate values. This approach is O(n^k) time and produces many redundant sequences, especially when the array has repeated elements.
Verified Code Solutions
function solution(arr, k) {
const n = arr.length;
const uniqueSequences = new Set();
const visited = new Array(n).fill(false);
function backtrack(start, currentSequence) {
if (currentSequence.length === k) {
uniqueSequences.add(JSON.stringify(currentSequence));
return;
}
for (let i = start; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
backtrack(i + 1, [...currentSequence, arr[i]]);
visited[i] = false;
}
}
}
backtrack(0, []);
return Array.from(uniqueSequences).map(JSON.parse);
}class Solution {
public:
vector<vector<int>> solution(vector<int>& arr, int k) {
int n = arr.size();
set<string> uniqueSequences;
vector<bool> visited(n, false);
void backtrack(int start, vector<int>& currentSequence) {
if (currentSequence.size() == k) {
uniqueSequences.insert(to_string(currentSequence));
return;
}
for (int i = start; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
backtrack(i + 1, currentSequence);
visited[i] = false;
}
}
}
backtrack(0, vector<int>());
vector<vector<int>> result;
for (const auto& seq : uniqueSequences) {
result.push_back(from_string(seq));
}
return result;
}
};class Solution {
public int solution(int[] arr, int k) {
int n = arr.length;
Set<String> uniqueSequences = new HashSet<>();
boolean[] visited = new boolean[n];
void backtrack(int start, int[] currentSequence) {
if (currentSequence.length == k) {
uniqueSequences.add(JSON.stringify(currentSequence));
return;
}
for (int i = start; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
backtrack(i + 1, Arrays.copyOf(currentSequence, currentSequence.length + 1));
visited[i] = false;
}
}
}
backtrack(0, new int[0]);
return uniqueSequences.stream().map(JSON::parse).collect(Collectors.toList());
}
}def solution(arr, k):
n = len(arr)
uniqueSequences = set()
visited = [False] * n
def backtrack(start, currentSequence):
if len(currentSequence) == k:
uniqueSequences.add(str(currentSequence))
return
for i in range(start, n):
if not visited[i]:
visited[i] = True
backtrack(i + 1, currentSequence + [arr[i]])
visited[i] = False
backtrack(0, [])
return [list(map(int, seq)) for seq in uniqueSequences]
function solution(arr, k) {
const n = arr.length;
const uniqueSequences = new Set();
const visited = new Array(n).fill(false);
function backtrack(start, currentSequence) {
if (currentSequence.length === k) {
uniqueSequences.add(JSON.stringify(currentSequence));
return;
}
for (let i = start; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
backtrack(i + 1, [...currentSequence, arr[i]]);
visited[i] = false;
}
}
}
backtrack(0, []);
return Array.from(uniqueSequences).map(JSON.parse);
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.