Find First and Last Position of Element

🎯

Find First and Last Position of Element

mediumBINARY_SEARCHFacebookAmazonGoogle

Imagine you have a sorted list of timestamps when a user logged into a system, and you want to find the first and last time they logged in on a particular day quickly.

💡 This problem is about searching efficiently in a sorted array to find the exact boundaries of a target value. Beginners often struggle because they try to find the target once and stop, missing the need to find both the first and last positions, which requires a modified binary search approach.

📋

Problem Statement

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. If the target is not found in the array, return [-1, -1]. Your algorithm's runtime complexity must be in the order of O(log n).

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9nums is sorted in ascending order-10^9 ≤ target ≤ 10^9

💡

Example

Input"nums = [5,7,7,8,8,10], target = 8"

Output[3,4]

The target 8 appears first at index 3 and last at index 4.

Input"nums = [5,7,7,8,8,10], target = 6"

Output[-1,-1]

The target 6 does not appear in the array.

• Empty array → [-1, -1]
• Array with one element equal to target → [0, 0]
• Array with all elements equal to target → [0, n-1]
• Target smaller than all elements → [-1, -1]
• Target larger than all elements → [-1, -1]

⚠️

Common Mistakes

Stopping binary search immediately after finding target

Returns any occurrence, not the first or last position

✅ Continue searching left or right half to find boundaries

Incorrect mid calculation causing overflow

Runtime error or infinite loop

✅ Use mid = left + (right - left) // 2 instead of (left + right) // 2

Not handling empty array or target not found cases

Index errors or incorrect output

✅ Initialize result to [-1, -1] and check if target found

Expanding boundaries without checking array bounds

Index out of range errors

✅ Check indices before accessing array elements

🧠

Brute Force (Linear Scan)

💡 This approach exists to establish a baseline understanding of the problem by checking every element. It is simple but inefficient, which motivates the need for binary search.

Intuition

Scan the array from start to end to find the first occurrence of the target, then scan from the end to find the last occurrence.

Algorithm

1. Initialize start and end positions as -1.
2. Traverse the array from left to right to find the first occurrence of target.
3. Traverse the array from right to left to find the last occurrence of target.
4. Return the start and end positions.

💡 The algorithm is straightforward but requires two passes, which is easy to understand but slow for large arrays.

</>

Code

def searchRange(nums, target):
    start, end = -1, -1
    for i in range(len(nums)):
        if nums[i] == target:
            start = i
            break
    for j in range(len(nums) - 1, -1, -1):
        if nums[j] == target:
            end = j
            break
    return [start, end]

# Driver code
if __name__ == '__main__':
    print(searchRange([5,7,7,8,8,10], 8))  # Output: [3,4]

Line Notes

start, end = -1, -1Initialize result indices to -1 indicating target not found yet

for i in range(len(nums))Scan from left to find first occurrence

if nums[i] == targetCheck if current element matches target

for j in range(len(nums) - 1, -1, -1)Scan from right to find last occurrence

import java.util.*;
public class Solution {
    public static int[] searchRange(int[] nums, int target) {
        int start = -1, end = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                start = i;
                break;
            }
        }
        for (int j = nums.length - 1; j >= 0; j--) {
            if (nums[j] == target) {
                end = j;
                break;
            }
        }
        return new int[]{start, end};
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(searchRange(new int[]{5,7,7,8,8,10}, 8)));
    }
}

Line Notes

int start = -1, end = -1;Initialize indices to indicate target not found

for (int i = 0; i < nums.length; i++)Left to right scan for first occurrence

if (nums[i] == target)Check if current element matches target

for (int j = nums.length - 1; j >= 0; j--)Right to left scan for last occurrence

#include <iostream>
#include <vector>
using namespace std;

vector<int> searchRange(vector<int>& nums, int target) {
    int start = -1, end = -1;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == target) {
            start = i;
            break;
        }
    }
    for (int j = nums.size() - 1; j >= 0; j--) {
        if (nums[j] == target) {
            end = j;
            break;
        }
    }
    return {start, end};
}

int main() {
    vector<int> nums = {5,7,7,8,8,10};
    vector<int> res = searchRange(nums, 8);
    cout << "[" << res[0] << "," << res[1] << "]" << endl;
    return 0;
}

Line Notes

int start = -1, end = -1;Initialize result indices to -1 meaning not found

for (int i = 0; i < nums.size(); i++)Scan from left to find first occurrence

if (nums[i] == target)Check if current element equals target

for (int j = nums.size() - 1; j >= 0; j--)Scan from right to find last occurrence

function searchRange(nums, target) {
    let start = -1, end = -1;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            start = i;
            break;
        }
    }
    for (let j = nums.length - 1; j >= 0; j--) {
        if (nums[j] === target) {
            end = j;
            break;
        }
    }
    return [start, end];
}

// Test
console.log(searchRange([5,7,7,8,8,10], 8)); // [3,4]

Line Notes

let start = -1, end = -1;Initialize indices to indicate target not found

for (let i = 0; i < nums.length; i++)Left to right scan for first occurrence

if (nums[i] === target)Check if current element matches target

for (let j = nums.length - 1; j >= 0; j--)Right to left scan for last occurrence

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the array twice in worst case, so time is linear in array size. Space is constant as no extra data structures are used.

💡 For n=100,000 elements, this means up to 200,000 checks, which is slow compared to binary search.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays, so interviewers expect you to improve it.

🧠

Modified Binary Search to Find Leftmost and Rightmost Indices

💡 This approach improves efficiency by using binary search twice to find the boundaries, leveraging the sorted property of the array.

Intuition

Use binary search to find the leftmost occurrence of the target, then use binary search again to find the rightmost occurrence.

Algorithm

1. Define a helper function to find the left boundary of the target using binary search.
2. Define a helper function to find the right boundary of the target using binary search.
3. Call the left boundary function to find the first occurrence.
4. Call the right boundary function to find the last occurrence.
5. Return the pair of indices.

💡 The key is modifying binary search to continue searching even after finding the target to find the extreme boundaries.

</>

Code

def searchRange(nums, target):
    def findLeft():
        left, right = 0, len(nums) - 1
        idx = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                right = mid - 1  # continue searching left
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    def findRight():
        left, right = 0, len(nums) - 1
        idx = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                left = mid + 1  # continue searching right
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    return [findLeft(), findRight()]

# Driver code
if __name__ == '__main__':
    print(searchRange([5,7,7,8,8,10], 8))  # Output: [3,4]

Line Notes

def findLeft():Helper to find leftmost index of target

while left <= right:Standard binary search loop condition

if nums[mid] == target:Update idx and move right pointer to find left boundary

elif nums[mid] < target:Move left pointer right to search higher values

import java.util.*;
public class Solution {
    public static int[] searchRange(int[] nums, int target) {
        int leftIdx = findLeft(nums, target);
        int rightIdx = findRight(nums, target);
        return new int[]{leftIdx, rightIdx};
    }
    private static int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1, idx = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                idx = mid;
                right = mid - 1; // continue searching left
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return idx;
    }
    private static int findRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1, idx = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                idx = mid;
                left = mid + 1; // continue searching right
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return idx;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(searchRange(new int[]{5,7,7,8,8,10}, 8)));
    }
}

Line Notes

int leftIdx = findLeft(nums, target);Find left boundary index

while (left <= right)Binary search loop condition

if (nums[mid] == target) {Update idx and move right pointer to find left boundary

else if (nums[mid] < target)Move left pointer right to search higher values

#include <iostream>
#include <vector>
using namespace std;

int findLeft(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1, idx = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            idx = mid;
            right = mid - 1; // continue searching left
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return idx;
}

int findRight(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1, idx = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            idx = mid;
            left = mid + 1; // continue searching right
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return idx;
}

vector<int> searchRange(vector<int>& nums, int target) {
    return {findLeft(nums, target), findRight(nums, target)};
}

int main() {
    vector<int> nums = {5,7,7,8,8,10};
    vector<int> res = searchRange(nums, 8);
    cout << "[" << res[0] << "," << res[1] << "]" << endl;
    return 0;
}

Line Notes

int idx = -1;Initialize index to -1 meaning target not found

while (left <= right)Binary search loop condition

if (nums[mid] == target)Update idx and move right pointer to find left boundary

else if (nums[mid] < target)Move left pointer right to search higher values

function searchRange(nums, target) {
    function findLeft() {
        let left = 0, right = nums.length - 1, idx = -1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] === target) {
                idx = mid;
                right = mid - 1; // continue searching left
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return idx;
    }
    function findRight() {
        let left = 0, right = nums.length - 1, idx = -1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] === target) {
                idx = mid;
                left = mid + 1; // continue searching right
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return idx;
    }
    return [findLeft(), findRight()];
}

// Test
console.log(searchRange([5,7,7,8,8,10], 8)); // [3,4]

Line Notes

let idx = -1;Initialize index to -1 meaning target not found

while (left <= right)Binary search loop condition

if (nums[mid] === target)Update idx and move right pointer to find left boundary

else if (nums[mid] < target)Move left pointer right to search higher values

⏱

Complexity

TimeO(log n)

SpaceO(1)

Each binary search runs in logarithmic time, so total time is O(log n). Space is constant as no extra data structures are used.

💡 For n=100,000 elements, this means about 2 * 17 = 34 operations, which is very efficient.

Interview Verdict: Accepted and optimal

This approach meets the problem's time complexity requirement and is the expected solution in interviews.

🧠

Single Binary Search with Post-Processing

💡 This approach uses one binary search to find any occurrence of the target, then expands linearly to find boundaries. It is a hybrid between brute force and binary search.

Intuition

Find one occurrence of the target using binary search, then move left and right to find the first and last positions.

Algorithm

1. Use binary search to find any index where target occurs.
2. If not found, return [-1, -1].
3. From the found index, move left while elements equal target to find start.
4. From the found index, move right while elements equal target to find end.
5. Return the start and end indices.

💡 This approach reduces the search space quickly but may degrade to linear in worst case if many duplicates exist.

</>

Code

def searchRange(nums, target):
    left, right = 0, len(nums) - 1
    found = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            found = mid
            break
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if found == -1:
        return [-1, -1]
    start, end = found, found
    while start - 1 >= 0 and nums[start - 1] == target:
        start -= 1
    while end + 1 < len(nums) and nums[end + 1] == target:
        end += 1
    return [start, end]

# Driver code
if __name__ == '__main__':
    print(searchRange([5,7,7,8,8,10], 8))  # Output: [3,4]

Line Notes

found = -1Initialize found index to -1 meaning target not found

while left <= right:Binary search loop to find any occurrence

if nums[mid] == target:Check if mid is target, then break

while start - 1 >= 0 and nums[start - 1] == target:Expand left boundary linearly

import java.util.*;
public class Solution {
    public static int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1, found = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                found = mid;
                break;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (found == -1) return new int[]{-1, -1};
        int start = found, end = found;
        while (start - 1 >= 0 && nums[start - 1] == target) start--;
        while (end + 1 < nums.length && nums[end + 1] == target) end++;
        return new int[]{start, end};
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(searchRange(new int[]{5,7,7,8,8,10}, 8)));
    }
}

Line Notes

int found = -1;Initialize found index to -1 meaning target not found

while (left <= right)Binary search loop to find target

if (nums[mid] == target)Check if mid is target and break

while (start - 1 >= 0 && nums[start - 1] == target)Expand left boundary linearly

#include <iostream>
#include <vector>
using namespace std;

vector<int> searchRange(vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1, found = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            found = mid;
            break;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (found == -1) return {-1, -1};
    int start = found, end = found;
    while (start - 1 >= 0 && nums[start - 1] == target) start--;
    while (end + 1 < (int)nums.size() && nums[end + 1] == target) end++;
    return {start, end};
}

int main() {
    vector<int> nums = {5,7,7,8,8,10};
    vector<int> res = searchRange(nums, 8);
    cout << "[" << res[0] << "," << res[1] << "]" << endl;
    return 0;
}

Line Notes

int found = -1;Initialize found index to -1 meaning target not found

while (left <= right)Binary search loop to find any occurrence

if (nums[mid] == target)Check if mid is target and break

while (start - 1 >= 0 && nums[start - 1] == target)Expand left boundary linearly

function searchRange(nums, target) {
    let left = 0, right = nums.length - 1, found = -1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            found = mid;
            break;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (found === -1) return [-1, -1];
    let start = found, end = found;
    while (start - 1 >= 0 && nums[start - 1] === target) start--;
    while (end + 1 < nums.length && nums[end + 1] === target) end++;
    return [start, end];
}

// Test
console.log(searchRange([5,7,7,8,8,10], 8)); // [3,4]

Line Notes

let found = -1;Initialize found index to -1 meaning target not found

while (left <= right)Binary search loop to find any occurrence

if (nums[mid] === target)Check if mid is target and break

while (start - 1 >= 0 && nums[start - 1] === target)Expand left boundary linearly

⏱

Complexity

TimeO(log n + k)

SpaceO(1)

Binary search takes O(log n), but expanding left and right can take up to O(k) where k is number of duplicates.

💡 If many duplicates exist, this approach can degrade to linear time, but for few duplicates it is efficient.

Interview Verdict: Accepted but less optimal than two binary searches

This approach is a good compromise if you want simpler code but may be slower on worst cases.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, you should code the modified binary search with two helper functions to find leftmost and rightmost indices because it is optimal and clean.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - never code
2. Modified Binary Search (Two Searches)	O(log n)	O(1)	No	N/A	Code this approach
3. Single Binary Search + Linear Expansion	O(log n + k)	O(1)	No	N/A	Mention as simpler alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, and finally present the optimal binary search solution.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the modified binary search approach to find boundaries.Step 4: Write clean, modular code with helper functions.Step 5: Test your code with edge cases and explain the complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of binary search modifications, ability to handle edge cases, and write clean code with correct boundary conditions.

Common Follow-ups

• What if the array is not sorted? → Use a hash map or linear scan.
• Can you do it in one binary search? → Possible but more complex, usually two searches are clearer.

💡 These follow-ups test your adaptability and deeper understanding of the problem constraints.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to find the first and last occurrence of a target in a sorted array efficiently.

Signature Phrases

'Find first and last position''Sorted array with duplicates''O(log n) time complexity'

NOT This Pattern When

Linear search problems or problems on unsorted arrays are not this pattern.

Similar Problems

Find Peak Element - also uses binary search modificationsSearch Insert Position - binary search to find insertion indexCount Occurrences of a Number - counting duplicates using binary search

Practice

1. You are given a sorted array and a target number x. The task is to find k elements closest to x in the array, with ties broken by choosing the smaller elements first. Which of the following approaches guarantees an optimal solution with logarithmic search complexity on the array?

easy

A. Use a greedy approach by iteratively picking the closest element to x until k elements are chosen.

B. Use dynamic programming to compute the minimum distance sum for all windows of size k and pick the minimum.

C. Perform a binary search to find the left boundary of the window of size k that contains the closest elements to x.

D. Use a two-pointer sliding window starting from both ends of the array and shrink towards the center until k elements remain.

Solution

1. Step 1: Understand problem constraints

   The array is sorted, and we want k closest elements to x with tie-breakers favoring smaller elements.

2. Step 2: Identify approach with logarithmic complexity

   Binary search on the left boundary of the window of size k efficiently narrows down the candidate window in O(log(n-k)) time, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits sorted order and window size constraints [OK]

Hint: Binary search on window boundaries exploits sorted array [OK]

Common Mistakes:

• Assuming greedy selection always yields optimal window
• Using DP unnecessarily increasing complexity
• Two-pointer approach is linear, not logarithmic

2. Given the following code snippet, what is the final output when running with piles = [3, 6, 7, 11] and h = 8?

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += ceil(pile / speed)
        if hours > h:
            return false
    return true

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

piles = [3,6,7,11]
h = 8
print(minEatingSpeed(piles, h))

easy

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Trace binary search iterations

   Initial low=1, high=11. mid=6: can_finish with speed=6 returns true (hours=3+1+2+2=8 ≤8), so high=6. Next mid=(1+6)//2=3: can_finish speed=3 returns false (hours=1+2+3+4=10 >8), so low=4. Next mid=(4+6)//2=5: can_finish speed=5 returns true (hours=1+2+2+3=8 ≤8), so high=5. Next mid=(4+5)//2=4: can_finish speed=4 returns true (hours=1+2+2+3=8 ≤8), so high=4. Now low=4, high=4, loop ends.

2. Step 2: Return final low value

   The minimum speed is 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracing confirms minimum speed is 4 [OK]

Hint: Check feasibility at mid speeds carefully [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Miscounting hours with ceil division

3. The following code attempts to find the maximum minimum distance to place m balls in position. Identify the bug that causes incorrect results or infinite loops.

medium

A. Not stopping early in can_place after placing all balls

B. Incorrect binary search boundaries: low should start at 0

C. Returning result before binary search loop ends

D. Line missing position.sort() before feasibility check

Solution

1. Step 1: Check sorting necessity

   The feasibility check assumes positions are sorted to place balls greedily. Missing position.sort() breaks this assumption.

2. Step 2: Consequences of missing sort

   Without sorting, the greedy check may fail to place balls correctly, causing wrong feasibility results and incorrect final answer.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting is essential before greedy feasibility check [OK]

Hint: Positions must be sorted before greedy feasibility check [OK]

Common Mistakes:

• Forgetting to sort positions
• Incorrect binary search boundaries causing infinite loops

4. What is the time complexity of the binary search on value range approach to find the median of two sorted arrays of sizes m and n, where the arrays contain values in the range [minVal, maxVal]?

medium

A. O(m + n)

B. O(log(m + n))

C. O((m + n) * log(maxVal - minVal))

D. O(log(maxVal - minVal) * (log m + log n))

Solution

1. Step 1: Identify outer binary search complexity

   Binary search on value range runs in O(log(maxVal - minVal)) iterations.

2. Step 2: CountLessEqual calls cost

   Each countLessEqual uses bisect on both arrays, each O(log m) and O(log n), total O(log m + log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested binary searches multiply complexities [OK]

Hint: Outer binary search times bisect calls per iteration [OK]

Common Mistakes:

• Confusing with merge O(m+n)
• Assuming O(log(m+n)) without value range
• Ignoring bisect cost inside loop

5. Suppose the array can contain negative numbers and the target can be any integer. Which modification to the optimal binary search algorithm is necessary to correctly handle this scenario?

hard

A. No modification needed; the existing algorithm works for any integers.

B. Replace all comparisons with absolute value comparisons to handle negatives.

C. Add explicit checks for negative values before deciding which half is sorted.

D. Use a linear scan instead since binary search assumptions break with negatives.

Solution

1. Step 1: Understand impact of negative numbers

   Negative numbers do not break rotation or duplicates but affect comparison logic when deciding sorted halves.

2. Step 2: Modify comparison logic

   Explicitly check and compare values considering negatives to correctly identify sorted half and target range.

3. Step 3: Reject naive absolute value or linear scan

   Absolute values distort order; linear scan is inefficient and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Comparisons must handle negatives explicitly [OK]

Hint: Adjust comparisons to handle negatives explicitly [OK]

Common Mistakes:

• Assuming negatives don't affect comparisons
• Using absolute values incorrectly
• Switching to linear scan unnecessarily