Longest Distinct Circular Subsequence — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Longest Distinct Circular Subsequence problem optimally.
O(n)O(n)Problem Description
Given a circular array nums of length n, find the maximum length of a contiguous subsequence (allowing wrap‑around from the end to the beginning) that contains no repeated values. The subsequence may start at any index and may traverse the boundary of the array, but its length cannot exceed n. Return this maximum length as an integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Distinct Circular Subsequence"
WHY DOES IT MATTER?
The sliding‑window with a hash map is a fundamental pattern for any “longest subarray with a constraint” problem; mastering it enables solving a wide class of distinct‑element, sum‑limit, or frequency‑bound challenges efficiently.
OPTIMIZATION CHALLENGE
Recognizing that the circular nature can be linearized by duplicating the array, then enforcing a hard window size limit, reduces the problem from quadratic to linear time.
REAL-WORLD CONNECTION
Think of a rotating cache line in a CPU where you must keep the longest sequence of unique memory addresses before a cache miss forces eviction—tracking last access times mirrors the hash‑map of indices.
When you hit a duplicate, jump the left pointer directly to lastSeen[duplicate]+1 instead of moving one step at a time; this single‑step jump is what guarantees O(n) performance.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem is a circular variant of the classic longest subarray with all distinct elements. A naive solution enumerates every possible start index and expands until a duplicate appears, leading to O(n²) time which explodes for large n. The optimal paradigm treats the circular array as a linear one of length 2n by concatenating the array to itself, then applies a sliding‑window (two‑pointer) technique while ensuring the window never exceeds the original length n. A hash map (or array for bounded values) stores the most recent index of each element; when a duplicate is encountered the left pointer jumps just past the previous occurrence, preserving distinctness. This yields a linear scan because each element is entered and removed from the window at most once, giving O(n) time and O(n) auxiliary space.
The key insight is that the circular wrap‑around can be simulated without explicit modular arithmetic by virtually extending the array. By limiting the window size to n we guarantee that we never count a subsequence longer than the array itself, which would be impossible. This approach also naturally handles edge cases such as all identical values (answer 1) or all distinct values (answer n).
Interview Questions on This Problem
Q1How would you modify the solution if the array were not circular?
Simply drop the concatenation step and run the same sliding‑window algorithm on the original array; the window size is naturally bounded by the array length, so the answer is the standard longest distinct subarray.
Q2What changes are needed to return the actual subsequence, not just its length?
Maintain the start index of the best window while scanning; after the loop, slice the original array using modular arithmetic to reconstruct the circular subsequence of length bestLen starting at bestStart.
Q3If the input stream is too large to fit in memory, how can you compute the answer?
Use a fixed‑size hash map that tracks only elements within the current window and a sliding‑window over the stream, discarding elements that fall out of the window; you still need to keep at most n distinct entries, so memory stays O(n).
Examples
Input
5 1 2 3 2 1
Output
3
Explanation: Starting at index 0 yields the segment [1,2,3] (3 distinct numbers). Any longer segment either repeats a value before wrapping or repeats after wrapping, so the longest possible distinct segment has length 3.
Input
5 5 1 2 3 4
Output
5
Explanation: All five numbers are different. Because the array is circular, we can include the whole array as a single distinct segment, giving length 5.
Input
4 7 7 7 7
Output
1
Explanation: Every element is identical. The only distinct segment possible consists of a single element, so the answer is 1.
Constraints
- 1 <= nums.length <= 200000
- -10^9 <= nums[i] <= 10^9
- The algorithm should run in O(n) time and O(n) auxiliary space.
Optimal Approach & Strategy
Duplicate the array, then use a sliding window with a hash map of last indices, moving the left pointer past duplicates and capping the window at n, achieving O(n) time.
Brute Force Approach
For each start index, expand forward until a duplicate appears or you’ve visited n elements, tracking the maximum length; this is O(n²).
Code Solutions
function longestDistinctCircularSubsequence(nums) {
const n = nums.length;
if (n === 0) return 0;
const arr = nums.concat(nums);
const count = new Map();
let left = 0, best = 0;
for (let right = 0; right < 2 * n; ++right) {
const val = arr[right];
count.set(val, (count.get(val) || 0) + 1);
while (count.get(val) > 1 || right - left + 1 > n) {
const lval = arr[left];
const c = count.get(lval) - 1;
if (c === 0) count.delete(lval);
else count.set(lval, c);
++left;
}
best = Math.max(best, right - left + 1);
}
return best;
}
// I/O handling
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length > 0) {
const n = data[0];
const nums = data.slice(1, n + 1);
console.log(longestDistinctCircularSubsequence(nums));
}#include <bits/stdc++.h>
using namespace std;
int longestDistinctCircularSubsequence(const vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> arr(nums);
arr.insert(arr.end(), nums.begin(), nums.end()); // duplicate, size = 2n
unordered_map<int,int> cnt;
int left = 0, best = 0;
for (int right = 0; right < 2 * n; ++right) {
int val = arr[right];
cnt[val]++;
while (cnt[val] > 1 || right - left + 1 > n) {
int lval = arr[left];
cnt[lval]--;
if (cnt[lval] == 0) cnt.erase(lval);
++left;
}
best = max(best, right - left + 1);
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin >> n)) return 0;
vector<int> nums(n);
for(int i = 0; i < n; ++i) cin >> nums[i];
cout << longestDistinctCircularSubsequence(nums) << "\n";
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int longestDistinctCircularSubsequence(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] arr = new int[2 * n];
System.arraycopy(nums, 0, arr, 0, n);
System.arraycopy(nums, 0, arr, n, n);
Map<Integer, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < 2 * n; ++right) {
int val = arr[right];
count.put(val, count.getOrDefault(val, 0) + 1);
while (count.get(val) > 1 || right - left + 1 > n) {
int lval = arr[left];
int c = count.get(lval) - 1;
if (c == 0) count.remove(lval);
else count.put(lval, c);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] nums = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
while (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
nums[i] = Integer.parseInt(st.nextToken());
}
System.out.println(longestDistinctCircularSubsequence(nums));
}
}def longestDistinctCircularSubsequence(nums):
n = len(nums)
if n == 0:
return 0
arr = nums + nums
count = {}
left = 0
best = 0
for right, val in enumerate(arr):
count[val] = count.get(val, 0) + 1
while count[val] > 1 or right - left + 1 > n:
lval = arr[left]
count[lval] -= 1
if count[lval] == 0:
del count[lval]
left += 1
best = max(best, right - left + 1)
return best
def main():
import sys
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
nums = list(map(int, data[1:1+n]))
print(longestDistinctCircularSubsequence(nums))
if __name__ == "__main__":
main()function longestDistinctCircularSubsequence(nums) {
const n = nums.length;
if (n === 0) return 0;
const arr = nums.concat(nums);
const count = new Map();
let left = 0, best = 0;
for (let right = 0; right < 2 * n; ++right) {
const val = arr[right];
count.set(val, (count.get(val) || 0) + 1);
while (count.get(val) > 1 || right - left + 1 > n) {
const lval = arr[left];
const c = count.get(lval) - 1;
if (c === 0) count.delete(lval);
else count.set(lval, c);
++left;
}
best = Math.max(best, right - left + 1);
}
return best;
}
// I/O handling
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length > 0) {
const n = data[0];
const nums = data.slice(1, n + 1);
console.log(longestDistinctCircularSubsequence(nums));
}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.