Longest Unique Segment — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Sliding Window and solve the Longest Unique Segment problem optimally.
O(N)O(U)Problem Description
You are analyzing a sequential stream of network traffic represented by an array of integers named packetTypes. Each integer in the array corresponds to a specific category of data packet received in chronological order. A continuous sequence of packets is considered valid if no packet type appears more than once within that sequence.
Your task is to compute the maximum possible length of a contiguous block of packets where every packet type in the block is completely distinct. Return an integer representing the size of this longest valid segment.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Unique Segment"
WHY DOES IT MATTER?
The dynamic sliding window pattern avoids duplicate redundant work by reusing information from overlapping window states. Mastering it enables efficient processing of linear data streams in single-pass linear time.
OPTIMIZATION CHALLENGE
The key optimization insight is eliminating incremental left-pointer steps by storing the last-seen index of each packet. When a duplicate occurs, the left boundary can jump directly past the previous occurrence of that packet in $O(1)$ steps.
REAL-WORLD CONNECTION
This pattern mimics dynamic telemetry monitors and network middleboxes that analyze live continuous traffic streams to detect burst limits, session unique sequences, or malicious repetitive patterns without buffer overflow.
When jumping the left pointer directly using last_seen_index + 1, always take max(left, last_seen_index + 1) to prevent moving the left boundary backwards when encountering a duplicate packet outside the current active window.
COMPLEXITY AT A GLANCE
O(N)O(U)Core Theory — Why This Approach?
The 'Longest Unique Segment' problem is a classic dynamic sliding window challenge that requires identifying a contiguous sequence with no duplicate elements. A naive approach inspects every possible subarray by generating all pairs of start and end indices $(i, j)$ and validating uniqueness with a set. This results in $O(N^2)$ time complexity for checking subarrays and $O(N^3)$ if set validation is done naively per segment, making it computationally intractable for large stream arrays containing hundreds of thousands of packets.
Interview Questions on This Problem
Q1How would you modify this solution if packet types were restricted to a known 16-bit integer range (0 to 65535)?
Instead of using a generic hash map which introduces hashing overhead and memory allocation costs, we can use a fixed-size array of 65,536 integers initialized to -1. This guarantees $O(1)$ constant time index lookups with minimal cache misses and zero garbage collection overhead.
Q2How would you solve this problem if the requirement changed to allowing at most K distinct packet types in the segment?
We maintain a frequency map of elements in the current window. We expand the right pointer, update packet counts, and if the map size exceeds K, we incrementally contract the left pointer while decrementing frequency counts until the map size drops back to K. The time complexity remains $O(N)$.
Q3How would you handle a real-time infinite stream of packets where old data must be processed with limited memory?
For an infinite stream, we process packets incrementally while maintaining a sliding window state. If memory is constrained, we can evict packet lookup indices that fall far behind the current left pointer or maintain a bounded sliding window with a fixed maximum TTL/buffer size using a FIFO queue combined with a hash set.
Examples
Input
packetTypes = [10, 20, 10, 30, 40, 20]
Output
4
Explanation: We track contiguous windows with distinct elements: - Window [10, 20] is valid (length 2). - Adding 10 causes a duplicate, so we adjust the window to [20, 10] (length 2). - Expanding further gives [20, 10, 30, 40], which contains no duplicate values and has length 4. - Adding the final 20 duplicates the existing 20, shrinking the window to [10, 30, 40, 20] (length 4). The maximum segment length achieved is 4.
Input
packetTypes = [5, 5, 5, 5]
Output
1
Explanation: Every element in the input is identical. The longest contiguous slice containing unique packet types can consist of only one element, giving a maximum length of 1.
Input
packetTypes = [1, 2, 3, 4, 5]
Output
5
Explanation: All elements in the input sequence are unique. Thus, the entire array of length 5 forms a valid segment without repeating packet types.
Input
packetTypes = [8, 3, 2, 3, 8, 4]
Output
4
Explanation: The contiguous sub-segment [2, 3, 8, 4] starts at index 2 and ends at index 5. It contains no duplicate values and has a length of 4, which is the maximum possible for this array.
Constraints
- 1 <= packetTypes.length <= 10^5
- -10^9 <= packetTypes[i] <= 10^9
Optimal Approach & Strategy
Utilize a dynamic sliding window tracking the most recent index of each packet type in a hash map. Jump the left pointer directly past the last occurrence of any duplicate inside the current window, maintaining $O(N)$ time complexity and $O(U)$ space complexity.
Brute Force Approach
Iterate over all possible pairs of start and end indices to generate every candidate subarray. Validate each subarray for duplicate packet types using a hash set, resulting in $O(N^2)$ time and rendering it unusable for large input arrays.
Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos=0;
const n = data[pos++]||0;
const packetTypes = data.slice(pos, pos+n);
function longestUniqueSegment(arr){
const last = new Map();
let left=0, best=0;
for(let right=0; right<arr.length; ++right){
const val=arr[right];
if(last.has(val) && last.get(val)>=left) left=last.get(val)+1;
last.set(val,right);
best=Math.max(best, right-left+1);
}
return best;
}
console.log(longestUniqueSegment(packetTypes).toString());#include <bits/stdc++.h>
using namespace std;
int longestUniqueSegment(const vector<int>& packetTypes) {
unordered_map<int,int> lastPos;
int left=0, best=0;
for(int right=0; right<(int)packetTypes.size(); ++right){
int val=packetTypes[right];
if(lastPos.count(val) && lastPos[val]>=left) left=lastPos[val]+1;
lastPos[val]=right;
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> a(n); for(int i=0;i<n;++i)cin>>a[i];
cout<<longestUniqueSegment(a);
return 0;}import java.io.*;
import java.util.*;
public class Main {
private static int longestUniqueSegment(int[] packetTypes) {
Map<Integer,Integer> last = new HashMap<>();
int left = 0, best = 0;
for(int right=0; right<packetTypes.length; ++right){
int val = packetTypes[right];
Integer prev = last.get(val);
if(prev != null && prev >= left) left = prev + 1;
last.put(val, right);
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[] packetTypes = new int[n];
if(n>0){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) packetTypes[i] = Integer.parseInt(st.nextToken());
}
System.out.print(longestUniqueSegment(packetTypes));
}
}import sys
def longest_unique_segment(packetTypes):
last = {}
left = 0
best = 0
for right, val in enumerate(packetTypes):
if val in last and last[val] >= left:
left = last[val] + 1
last[val] = right
best = max(best, right - left + 1)
return best
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
packetTypes = list(map(int, data[1:1+n]))
print(longest_unique_segment(packetTypes))
if __name__ == "__main__":
main()const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos=0;
const n = data[pos++]||0;
const packetTypes = data.slice(pos, pos+n);
function longestUniqueSegment(arr){
const last = new Map();
let left=0, best=0;
for(let right=0; right<arr.length; ++right){
const val=arr[right];
if(last.has(val) && last.get(val)>=left) left=last.get(val)+1;
last.set(val,right);
best=Math.max(best, right-left+1);
}
return best;
}
console.log(longestUniqueSegment(packetTypes).toString());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.