DSA-006 · FOCUSED PRACTICE
Longest Consecutive Sequence
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 19938 deterministic checks. Learner drafts are not executed.
Understand the problem
Given an unsorted array of integers, return the length of the longest run of distinct consecutive integer values. The values may appear in any order. A repeated value contributes once; a run does not need to be contiguous in the input.
- Input is a non-null int[] with 0–100,000 elements. Every signed Java int value is valid. Null is outside the contract; the method does not validate it.
- Return an int from 0 to nums.length. An empty input returns 0. Neither approach modifies the input.
- Consecutive means mathematical difference 1: Integer.MAX_VALUE and Integer.MIN_VALUE are not adjacent. Return a length, not a sequence or its input indices.
Examples
Input:
[100,4,200,1,3,2]
Output:4The values 1,2,3,4 form a run of length four even though they are scattered through the array.
Input:
[1,2,2,3]
Output:3The repeated 2 does not lengthen or break the run 1,2,3.
Input:
[-2147483648,2147483647]
Output:1The two extreme int values must not wrap around and appear consecutive.
Before you start
- Java Set<Integer>, equality and hash-based membership
- Sorting and expected versus worst-case complexity
- Signed integer boundaries
Recognize the structure
Order is irrelevant and the question repeatedly asks whether a neighbor exists. A set can answer membership without sorting. The important extra observation is that a run should be scanned only from its left boundary. This is not longest increasing subsequence: [1,3,2] has a consecutive set of length 3, but its increasing subsequence in input order has length 2.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 107/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Which operation do you repeat when extending a consecutive run? Store membership rather than input positions.
Hint 2
Every run has a unique smallest value. How can you recognize it without sorting?
Hint 3
Only launch scans from values whose predecessor is absent. Iterate distinct values and guard integer boundaries.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Sort a copy, then count runs
Clone the array to honor the non-mutation contract, sort it, and scan left to right. Skip equal neighbors; increment the run length for a difference of one and reset it otherwise. For [3,1,2,2], the sorted copy is [1,2,2,3]; lengths are 1,2,2,3. Sorting solves membership implicitly, but costs O(n log n) time. The cloned array costs O(n) space; do not call this approach constant-space merely because the scan is.
Improve the baseline
Remove order work
Insert all values in Set<Integer>. Duplicates disappear and membership is expected O(1). Iterating this set rather than the original array prevents repeated duplicates of a boundary from rescanning the same run.
Choose one owner per run
If start-1 exists, start belongs to a run owned by an earlier value, so skip it. Otherwise scan start+1, start+2, and so on. For [1,2,3,4], only 1 launches a scan.
Guard the domain boundaries
Do not compute a predecessor for Integer.MIN_VALUE or a successor after Integer.MAX_VALUE. These guards preserve mathematical adjacency despite Java int wraparound.
Why it is correct
Initialization
Before a run scan, start is a left boundary and length=1 describes the run [start,start]. Empty input performs no scans and leaves best=0.
Preservation
While scanning, every integer from start through end is in the set and length counts exactly those integers. Extending only when end+1 exists preserves a gap-free run. best stores the greatest finished run length.
Coverage and termination
Each finite maximal run has exactly one value without a predecessor. That boundary is visited once in the set iteration. Each extension increases end until a missing neighbor or MAX_VALUE, so scanning ends. All maximal runs are measured and their maximum is returned.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public final class Solution {
public static int longestConsecutive(int[] nums) {
Set<Integer> values = new HashSet<>();
for (int value : nums) values.add(value);
int best = 0;
for (int start : values) {
// Integer.MIN_VALUE has no predecessor in this contract.
if (start != Integer.MIN_VALUE && values.contains(start - 1)) continue;
int end = start;
int length = 1;
while (end != Integer.MAX_VALUE && values.contains(end + 1)) {
end++;
length++;
}
best = Math.max(best, length);
}
return best;
}
public static int baseline(int[] nums) {
if (nums.length == 0) return 0;
int[] sorted = nums.clone();
Arrays.sort(sorted);
int best = 1, length = 1;
for (int i = 1; i < sorted.length; i++) {
if (sorted[i] == sorted[i - 1]) continue;
if ((long) sorted[i] - sorted[i - 1] == 1) length++;
else length = 1;
best = Math.max(best, length);
}
return best;
}
}
Read the meaningful blocks
Build values
HashSet<Integer> removes duplicate work. Set<int> is illegal because Java generics require reference types.
Select boundaries
The predecessor check is the reason the nested loops are linear in aggregate; merely replacing array membership with a set is insufficient.
Extend and record
The successor guard prevents overflow; length grows once per distinct element of a scanned run. Math.max retains the best completed run.
Complexity
Let n be input length and u the number of distinct values. Building the set takes expected O(n) time; every distinct value has one boundary check, and each value participates in at most one run scan. Total expected time is O(n+u)=O(n), not a guaranteed hash-table worst-case bound.
Auxiliary storage is O(u) boxed integers and table entries. Output is one int. The input is preserved. Sorting baseline is O(n log n) time and O(n) extra storage for its copy.
Exact-state walkthroughs
Reveal normal and boundary traces
Scattered run
Input: [100,4,200,1,3,2] · Result: 4
Step 1 of 14: Deduplicate the input. Trace visits values in input insertion order; Java HashSet may use another order.
Each input value is represented once.
- 0: 100
- 1: 4
- 2: 200
- 3: 1
- 4: 3
- 5: 2
| Variable | Value |
|---|---|
| values | [100,4,200,1,3,2] |
| best | 0 |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.HashSet; 3 import java.util.Set; 4 5 public final class Solution { 6 public static int longestConsecutive(int[] nums) { 7 Set<Integer> values = new HashSet<>(); 8 for (int value : nums) values.add(value); 9 int best = 0; 10 for (int start : values) { 11 // Integer.MIN_VALUE has no predecessor in this contract. 12 if (start != Integer.MIN_VALUE && values.contains(start - 1)) continue; 13 int end = start; 14 int length = 1; 15 while (end != Integer.MAX_VALUE && values.contains(end + 1)) { 16 end++; 17 length++; 18 } 19 best = Math.max(best, length); 20 } 21 return best; 22 } 23 24 public static int baseline(int[] nums) { 25 if (nums.length == 0) return 0; 26 int[] sorted = nums.clone(); 27 Arrays.sort(sorted); 28 int best = 1, length = 1; 29 for (int i = 1; i < sorted.length; i++) { 30 if (sorted[i] == sorted[i - 1]) continue; 31 if ((long) sorted[i] - sorted[i - 1] == 1) length++; 32 else length = 1; 33 best = Math.max(best, length); 34 } 35 return best; 36 } 37 } 38
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Deduplicate the input. Trace visits values in input insertion order; Java HashSet may use another order.
Each input value is represented once.
- values
[100,4,200,1,3,2]- best
0
- Start the run at 100.
The current interval is present and has no predecessor.
- start
100- end
100- length
1- best
0
- Record the completed maximal run.
best is the maximum of finished runs.
- start
100- end
100- length
1- best
1
- Skip 4: predecessor exists.
This run is owned by a smaller boundary.
- start
4- best
1
- Start the run at 200.
The current interval is present and has no predecessor.
- start
200- end
200- length
1- best
1
- Record the completed maximal run.
best is the maximum of finished runs.
- start
200- end
200- length
1- best
1
- Start the run at 1.
The current interval is present and has no predecessor.
- start
1- end
1- length
1- best
1
- Extend through 2.
Every value from start to end is present; length=end-start+1.
- start
1- end
2- length
2- best
1
- Extend through 3.
Every value from start to end is present; length=end-start+1.
- start
1- end
3- length
3- best
1
- Extend through 4.
Every value from start to end is present; length=end-start+1.
- start
1- end
4- length
4- best
1
- Record the completed maximal run.
best is the maximum of finished runs.
- start
1- end
4- length
4- best
4
- Skip 3: predecessor exists.
This run is owned by a smaller boundary.
- start
3- best
4
- Skip 2: predecessor exists.
This run is owned by a smaller boundary.
- start
2- best
4
- Return the contract result.
The result follows from the completed state and the declared contract.
- result
4
Overflow boundary
Input: [2147483647,-2147483648] · Result: 1
Step 1 of 6: Deduplicate the input. Trace visits values in input insertion order; Java HashSet may use another order.
Each input value is represented once.
- 0: 2147483647
- 1: -2147483648
| Variable | Value |
|---|---|
| values | [2147483647,-2147483648] |
| best | 0 |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.HashSet; 3 import java.util.Set; 4 5 public final class Solution { 6 public static int longestConsecutive(int[] nums) { 7 Set<Integer> values = new HashSet<>(); 8 for (int value : nums) values.add(value); 9 int best = 0; 10 for (int start : values) { 11 // Integer.MIN_VALUE has no predecessor in this contract. 12 if (start != Integer.MIN_VALUE && values.contains(start - 1)) continue; 13 int end = start; 14 int length = 1; 15 while (end != Integer.MAX_VALUE && values.contains(end + 1)) { 16 end++; 17 length++; 18 } 19 best = Math.max(best, length); 20 } 21 return best; 22 } 23 24 public static int baseline(int[] nums) { 25 if (nums.length == 0) return 0; 26 int[] sorted = nums.clone(); 27 Arrays.sort(sorted); 28 int best = 1, length = 1; 29 for (int i = 1; i < sorted.length; i++) { 30 if (sorted[i] == sorted[i - 1]) continue; 31 if ((long) sorted[i] - sorted[i - 1] == 1) length++; 32 else length = 1; 33 best = Math.max(best, length); 34 } 35 return best; 36 } 37 } 38
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Deduplicate the input. Trace visits values in input insertion order; Java HashSet may use another order.
Each input value is represented once.
- values
[2147483647,-2147483648]- best
0
- Start the run at 2147483647.
The current interval is present and has no predecessor.
- start
2147483647- end
2147483647- length
1- best
0
- Record the completed maximal run.
best is the maximum of finished runs.
- start
2147483647- end
2147483647- length
1- best
1
- Start the run at -2147483648.
The current interval is present and has no predecessor.
- start
-2147483648- end
-2147483648- length
1- best
1
- Record the completed maximal run.
best is the maximum of finished runs.
- start
-2147483648- end
-2147483648- length
1- best
1
- Return the contract result.
The result follows from the completed state and the declared contract.
- result
1
Test the contract
Input:
[]
Output:0No boundary exists.
Input:
[7]
Output:1Single boundary.
Input:
[5,5,5]
Output:1Duplicate suppression.
Input:
[-2,-1,0,2]
Output:3Negative values and a gap.
Input:
[2147483646,2147483647]
Output:2Right domain boundary.
Input:
[-2147483648,-2147483647]
Output:2Left domain boundary.
Common mistakes and counterexamples
Start a scan from every value
Counterexample: [1,2,3,4] launches scans of lengths 4,3,2,1.
Start only where the predecessor is absent; otherwise a length-n run costs quadratic work.
Scan boundaries in the original array
Counterexample: [1,1,1,2,3] scans the same run three times.
Iterate the distinct set; repeated boundary values must not repeat work.
Allow int arithmetic to wrap
Counterexample: [2147483647,-2147483648] can be linked incorrectly.
Guard MIN_VALUE before subtracting and MAX_VALUE before adding.
Count duplicates as a new consecutive step
Counterexample: [1,2,2,3] should return 3.
Deduplicate in the set; in the sorting baseline, skip equality without resetting.
Follow-ups
Return the actual run, with ties favoring the smallest start.
Track bestStart with best length, update on longer runs or equal length and smaller start, and reconstruct values. The output itself costs O(best). HashSet iteration order is unspecified, so tie handling must be explicit.
The input is already sorted and memory is tight.
Scan adjacent distinct values directly in O(n) time and O(1) extra space. Keep the overflow-safe long difference from the baseline; a set adds no value here.
Values arrive online and a query follows each insertion.
A simple set may rescan too much. Maintain lengths at interval endpoints, joining left and right runs for a new distinct value. Explain duplicate suppression and overflow guards; this is a different state invariant.