DSA-061 · Two monotone boundaries for a duplicate range

First and Last Position of a Target

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 22037 deterministic checks. Learner drafts are not executed.

Understand the problem

Return a fresh int pair [first,last] giving the inclusive positions of target in a nondecreasing array. Return [−1,−1] if absent. Find both boundaries logarithmically without scanning a duplicate run.

nums is nonnull, nondecreasing, and contains at most 100,000 arbitrary int values. Duplicates are allowed. Order is a precondition, not a scanned validation.
The returned pair is always newly allocated and contains inclusive indices when present. Empty and absent inputs return a fresh [−1,−1]. The underlying bound searches use half-open [left,right) intervals.
Neither method changes nums; null throws NullPointerException. Target may equal Integer.MAX_VALUE, so no target+1 shortcut is used.

Examples

Input: [5,7,7,8,8,10], target=8
Output: [3,4]
First >=8 is index 3; first >8 is index 5, so inclusive last is 4.
Input: [1,3], target=2
Output: [−1,−1]
The lower boundary is 1 but nums[1] is 3; validate equality before reporting a range.
Input: [MIN,MAX,MAX], target=MAX
Output: [1,2]
An explicit strict upper-bound predicate avoids overflowing MAX+1.

Before you start

Lower and upper bounds
Inclusive output endpoints versus half-open search boundaries

Recognize the structure

The target’s occurrences form one contiguous block. Finding one match and expanding outward can be linear on all-equal input. Instead find the two transitions: <target to >=target, then <=target to >target.

Try before revealing

Hint 1

All occurrences are one block. Which two boundaries describe that block?

Hint 2

Find first >=target, then first >target, with no target arithmetic.

Hint 3

Validate the lower boundary, and convert [first,after) into [first,after−1].

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Track first and last during a full scan

Initialize both endpoints to −1; on each matching element set first only once and update last. For [1,2,2,2,4], target=2, the scan records first=1 and last progresses 1,2,3. This valid O(n)-time, O(1)-workspace baseline is easy to compare against two logarithmic boundary searches.

Improve the baseline

Find and validate the first boundary

Run bound(nums,target,false) to find the first >=target. If it equals n or that value is not target, return absence without indexing n.

Find the boundary after the run

Run the same interval mechanism with strict=true, treating equality as too small. It returns the first >target, including n.

Convert boundary to inclusive endpoint

The run is [first,after) internally; return [first,after−1]. No expansion scan and no integer increment of target are needed.

Why it is correct

Lower transition

With strict=false, every discarded left index is <target and the right certified side is >=target. At convergence first is exactly the first possible occurrence; a failed equality check proves absence.

Upper transition

With strict=true, equality also belongs to the discarded left side. The returned after is therefore the first strictly larger index. All elements from first through after−1 equal target by sortedness.

Complete maximal range

The element before first, if any, is too small; the element at after, if any, is too large. Thus the reported inclusive pair is exactly the maximal occurrence run. Each bound strictly shrinks, and no input write occurs.

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.Objects;

public final class Solution {
    public static int[] equalRange(int[] nums, int target) {
        Objects.requireNonNull(nums, "nums");
        int first = bound(nums, target, false);
        if (first == nums.length || nums[first] != target) return new int[]{-1, -1};
        int after = bound(nums, target, true);
        return new int[]{first, after - 1};
    }
    private static int bound(int[] nums, int target, boolean strict) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target || (strict && nums[mid] == target)) left = mid + 1;
            else right = mid;
        }
        return left;
    }
    public static int[] baseline(int[] nums, int target) {
        Objects.requireNonNull(nums, "nums");
        int first = -1, last = -1;
        for (int i = 0; i < nums.length; i++) if (nums[i] == target) {
            if (first < 0) first = i;
            last = i;
        }
        return new int[]{first, last};
    }
}

Read the meaningful blocks

Shared bound helper

The strict flag changes whether equality advances left. It does not alter the half-open interval convention.

Guard absence first

Check first==n before nums[first], relying on short-circuit || to avoid an out-of-bounds access.

Allocate result separately

The pair describes positions, not values, and never aliases nums even when nums itself has length two.

Complexity

At most two binary searches take O(log(n+1)) time and O(1) auxiliary workspace. The two-int returned array is constant-sized output.

The baseline takes O(n) time. Finding a match and then scanning duplicates is also O(n) worst case and does not meet the logarithmic target.

Exact-state walkthroughs

Reveal normal and boundary traces

Search both ends of an interior duplicate run

Input: {"nums":[5,7,7,8,8,10],"target":8} · Inclusive occurrence range: [3,4]

Step 1 of 10: Begin the lower boundary search.

Below left values are < target; at/after right values are >= target.

Target range — two transition searches

Unresolved boundary range: [0, 6]. Phase: lower. Target: 8.

index 05retained element
index 17retained element
index 27retained element
index 38retained element
index 48retained element
index 510retained element

Highlight marks the last probed element, which may have just been discarded. The answer is a boundary, so n is a legal result even though it is not an element index. Certified sides meet when the two boundaries converge.

State after this step
Variable	Value
values	`[5,7,7,8,8,10]`
target	`8`
left	`0`
right	`6`
bounds	`"half-open"`
phase	`"lower"`
strict	`false`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int[] equalRange(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int first = bound(nums, target, false);
 7         if (first == nums.length || nums[first] != target) return new int[]{-1, -1};
 8         int after = bound(nums, target, true);
 9         return new int[]{first, after - 1};
10     }
11     private static int bound(int[] nums, int target, boolean strict) {
12         int left = 0, right = nums.length;
13         while (left < right) {
14             int mid = left + (right - left) / 2;
15             if (nums[mid] < target || (strict && nums[mid] == target)) left = mid + 1;
16             else right = mid;
17         }
18         return left;
19     }
20     public static int[] baseline(int[] nums, int target) {
21         Objects.requireNonNull(nums, "nums");
22         int first = -1, last = -1;
23         for (int i = 0; i < nums.length; i++) if (nums[i] == target) {
24             if (first < 0) first = i;
25             last = i;
26         }
27         return new int[]{first, last};
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin the lower boundary search.
Below left values are < target; at/after right values are >= target.
values
[5,7,7,8,8,10]
target
8
left
0
right
6
bounds
"half-open"
phase
"lower"
strict
false
Certify a side of the lower transition.
Equality moves right toward the first target occurrence. The candidate boundary stays in the closed boundary range [left,right].
values
[5,7,7,8,8,10]
target
8
left
0
right
3
bounds
"half-open"
phase
"lower"
strict
false
before
[0,6]
mid
3
probeValue
8
Certify a side of the lower transition.
Equality moves right toward the first target occurrence. The candidate boundary stays in the closed boundary range [left,right].
values
[5,7,7,8,8,10]
target
8
left
2
right
3
bounds
"half-open"
phase
"lower"
strict
false
before
[0,3]
mid
1
probeValue
7
Certify a side of the lower transition.
Equality moves right toward the first target occurrence. The candidate boundary stays in the closed boundary range [left,right].
values
[5,7,7,8,8,10]
target
8
left
3
right
3
bounds
"half-open"
phase
"lower"
strict
false
before
[2,3]
mid
2
probeValue
7
Validate the converged lower boundary before indexing.
An after-end boundary or a nonmatching value proves absence; no upper search is needed then.
values
[5,7,7,8,8,10]
target
8
left
3
right
3
bounds
"half-open"
phase
"validate"
first
3
present
true
Begin the strict upper boundary search.
Below left values are <= target; at/after right values are > target.
values
[5,7,7,8,8,10]
target
8
left
0
right
6
bounds
"half-open"
phase
"upper"
strict
true
first
3
Certify a side of the upper transition.
Equality moves left past the target run. The candidate boundary stays in the closed boundary range [left,right].
values
[5,7,7,8,8,10]
target
8
left
4
right
6
bounds
"half-open"
phase
"upper"
strict
true
before
[0,6]
mid
3
probeValue
8
first
3
Certify a side of the upper transition.
Equality moves left past the target run. The candidate boundary stays in the closed boundary range [left,right].
values
[5,7,7,8,8,10]
target
8
left
4
right
5
bounds
"half-open"
phase
"upper"
strict
true
before
[4,6]
mid
5
probeValue
10
first
3
Certify a side of the upper transition.
Equality moves left past the target run. The candidate boundary stays in the closed boundary range [left,right].
values
[5,7,7,8,8,10]
target
8
left
5
right
5
bounds
"half-open"
phase
"upper"
strict
true
before
[4,5]
mid
4
probeValue
8
first
3
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
[3,4]

Lower boundary exists but target is absent

Input: {"nums":[1,3],"target":2} · Inclusive occurrence range: [-1,-1]

Step 1 of 5: Begin the lower boundary search.

Below left values are < target; at/after right values are >= target.

Target range — two transition searches

Unresolved boundary range: [0, 2]. Phase: lower. Target: 2.

index 01retained element
index 13retained element

State after this step
Variable	Value
values	`[1,3]`
target	`2`
left	`0`
right	`2`
bounds	`"half-open"`
phase	`"lower"`
strict	`false`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int[] equalRange(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int first = bound(nums, target, false);
 7         if (first == nums.length || nums[first] != target) return new int[]{-1, -1};
 8         int after = bound(nums, target, true);
 9         return new int[]{first, after - 1};
10     }
11     private static int bound(int[] nums, int target, boolean strict) {
12         int left = 0, right = nums.length;
13         while (left < right) {
14             int mid = left + (right - left) / 2;
15             if (nums[mid] < target || (strict && nums[mid] == target)) left = mid + 1;
16             else right = mid;
17         }
18         return left;
19     }
20     public static int[] baseline(int[] nums, int target) {
21         Objects.requireNonNull(nums, "nums");
22         int first = -1, last = -1;
23         for (int i = 0; i < nums.length; i++) if (nums[i] == target) {
24             if (first < 0) first = i;
25             last = i;
26         }
27         return new int[]{first, last};
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin the lower boundary search.
Below left values are < target; at/after right values are >= target.
values
[1,3]
target
2
left
0
right
2
bounds
"half-open"
phase
"lower"
strict
false
Certify a side of the lower transition.
Equality moves right toward the first target occurrence. The candidate boundary stays in the closed boundary range [left,right].
values
[1,3]
target
2
left
0
right
1
bounds
"half-open"
phase
"lower"
strict
false
before
[0,2]
mid
1
probeValue
3
Certify a side of the lower transition.
Equality moves right toward the first target occurrence. The candidate boundary stays in the closed boundary range [left,right].
values
[1,3]
target
2
left
1
right
1
bounds
"half-open"
phase
"lower"
strict
false
before
[0,1]
mid
0
probeValue
1
Validate the converged lower boundary before indexing.
An after-end boundary or a nonmatching value proves absence; no upper search is needed then.
values
[1,3]
target
2
left
1
right
1
bounds
"half-open"
phase
"validate"
first
1
present
false
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
[-1,-1]

Maximum int requires a strict comparison, not target+1

Input: {"nums":[-2147483648,2147483647,2147483647],"target":2147483647} · Inclusive occurrence range: [1,2]

Step 1 of 8: Begin the lower boundary search.

Below left values are < target; at/after right values are >= target.

Target range — two transition searches

Unresolved boundary range: [0, 3]. Phase: lower. Target: 2147483647.

index 0-2147483648retained element
index 12147483647retained element
index 22147483647retained element

State after this step
Variable	Value
values	`[-2147483648,2147483647,2147483647]`
target	`2147483647`
left	`0`
right	`3`
bounds	`"half-open"`
phase	`"lower"`
strict	`false`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int[] equalRange(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int first = bound(nums, target, false);
 7         if (first == nums.length || nums[first] != target) return new int[]{-1, -1};
 8         int after = bound(nums, target, true);
 9         return new int[]{first, after - 1};
10     }
11     private static int bound(int[] nums, int target, boolean strict) {
12         int left = 0, right = nums.length;
13         while (left < right) {
14             int mid = left + (right - left) / 2;
15             if (nums[mid] < target || (strict && nums[mid] == target)) left = mid + 1;
16             else right = mid;
17         }
18         return left;
19     }
20     public static int[] baseline(int[] nums, int target) {
21         Objects.requireNonNull(nums, "nums");
22         int first = -1, last = -1;
23         for (int i = 0; i < nums.length; i++) if (nums[i] == target) {
24             if (first < 0) first = i;
25             last = i;
26         }
27         return new int[]{first, last};
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin the lower boundary search.
Below left values are < target; at/after right values are >= target.
values
[-2147483648,2147483647,2147483647]
target
2147483647
left
0
right
3
bounds
"half-open"
phase
"lower"
strict
false
Certify a side of the lower transition.
Equality moves right toward the first target occurrence. The candidate boundary stays in the closed boundary range [left,right].
values
[-2147483648,2147483647,2147483647]
target
2147483647
left
0
right
1
bounds
"half-open"
phase
"lower"
strict
false
before
[0,3]
mid
1
probeValue
2147483647
Certify a side of the lower transition.
Equality moves right toward the first target occurrence. The candidate boundary stays in the closed boundary range [left,right].
values
[-2147483648,2147483647,2147483647]
target
2147483647
left
1
right
1
bounds
"half-open"
phase
"lower"
strict
false
before
[0,1]
mid
0
probeValue
-2147483648
Validate the converged lower boundary before indexing.
An after-end boundary or a nonmatching value proves absence; no upper search is needed then.
values
[-2147483648,2147483647,2147483647]
target
2147483647
left
1
right
1
bounds
"half-open"
phase
"validate"
first
1
present
true
Begin the strict upper boundary search.
Below left values are <= target; at/after right values are > target.
values
[-2147483648,2147483647,2147483647]
target
2147483647
left
0
right
3
bounds
"half-open"
phase
"upper"
strict
true
first
1
Certify a side of the upper transition.
Equality moves left past the target run. The candidate boundary stays in the closed boundary range [left,right].
values
[-2147483648,2147483647,2147483647]
target
2147483647
left
2
right
3
bounds
"half-open"
phase
"upper"
strict
true
before
[0,3]
mid
1
probeValue
2147483647
first
1
Certify a side of the upper transition.
Equality moves left past the target run. The candidate boundary stays in the closed boundary range [left,right].
values
[-2147483648,2147483647,2147483647]
target
2147483647
left
3
right
3
bounds
"half-open"
phase
"upper"
strict
true
before
[2,3]
mid
2
probeValue
2147483647
first
1
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
[1,2]

Test the contract

Input: []
Output: [−1,−1]
No illegal dereference.
Input: [2,2,2], target=2
Output: [0,2]
Complete duplicate block.
Input: [1,3], target=2
Output: [−1,−1]
Lower boundary not equal.
Input: [MIN,MAX,MAX], target=MAX
Output: [1,2]
No overflow shortcut.
Input: [9], target=9
Output: [0,0]
One-element inclusive range.

Common mistakes and counterexamples

Use lowerBound(target+1)

Counterexample: For target=MAX, int addition wraps to MIN and yields a meaningless boundary.

Implement the strict >target boundary directly.

Return after as the last index

Counterexample: [2,2] has upper boundary 2 but last index 1.

Convert the internal half-open run using after−1.

Assume any lower boundary is a match

Counterexample: [1,3], target=2 yields boundary 1 but no occurrence.

Validate boundary<n and nums[boundary]==target.

Expand from a found duplicate

Counterexample: An all-equal 100,000-element array requires a full linear scan.

Search the two monotone transitions independently.

Follow-ups

Return only occurrence count.

Return after−first when the lower boundary is a match, otherwise zero. Alternatively upper−lower already gives zero for absence if both searches run.

Return values in a numeric range.

Use lowerBound(low) and upperBound(high) for an inclusive numeric interval. State behavior when low>high and distinguish returned indices from copying the values.

Insert before versus after equal values.

Lower bound inserts before the run; upper bound inserts after it. Stable insertion policy depends on which equal occurrences should precede the new one.

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.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 107/20,000 characters

Self-review

I can explain both boundary predicates and their equality handling.I guard the after-end lower boundary before indexing.I distinguish inclusive last from the exclusive after boundary.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Binary search: candidate intervals and monotone feasibility

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.