Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array - Problem

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Input & Output

Example 1 — Basic Range

$ Input: nums = [5,7,7,8,8,10], target = 8

› Output: [3,4]

💡 Note: Target 8 appears at indices 3 and 4. The first occurrence is at index 3, last occurrence at index 4.

Example 2 — Target Not Found

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

› Output: [-1,-1]

💡 Note: Target 6 is not present in the array, so return [-1, -1].

Example 3 — Single Element

$ Input: nums = [], target = 0

› Output: [-1,-1]

💡 Note: Empty array, target cannot be found.

Constraints

0 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
nums is a non-decreasing array
-10⁹ ≤ target ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [5,7,7,8,8,10] and target 8

Binary search to find first and last occurrences

Output

Return range [3,4] or [-1,-1] if not found

Key Takeaway

🎯 Key Insight: Binary search twice - once for leftmost boundary, once for rightmost boundary

Asked in

M Meta 85 A Amazon 72 M Microsoft 65 G Google 58

The key insight is to use binary search twice on the sorted array. The optimal approach uses two binary searches - one to find the leftmost position and another for the rightmost position. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search (Two Pass)	O(log n)	O(1)	Use binary search twice - once for leftmost position, once for rightmost position
Linear Search	O(n)	O(1)	Scan array from left to right to find first and last occurrences

Binary Search (Two Pass) — Algorithm Steps

Binary search to find leftmost position of target
Binary search to find rightmost position of target
Return the range [left, right]

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Left

Binary search for leftmost occurrence

Find Right

Binary search for rightmost occurrence

Result

Combine results into range

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int findLeft(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    int result = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

int findRight(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    int result = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            result = mid;
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

int* solution(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    
    int leftPos = findLeft(nums, numsSize, target);
    if (leftPos == -1) {
        result[0] = -1;
        result[1] = -1;
        return result;
    }
    
    int rightPos = findRight(nums, numsSize, target);
    result[0] = leftPos;
    result[1] = rightPos;
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    int returnSize;
    int* result = solution(nums, numsSize, target, &returnSize);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Two binary searches, each taking O(log n) time

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for search boundaries

✓ Linear Space

456.0K Views

High Frequency

~25 min Avg. Time

15.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search (Two Pass) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler