Find First and Last Position of Element in Sorted Array

You are given a sorted array of integers and a target element x. Your task is to find the first and last occurrences of x within the array. If the target element is not present in the array, return [-1, -1] to indicate that the element is not found.

constraint:

• A sorted array of integers, denoted as nums, where 1 <= nums.length <= 10^5.
• An integer value, denoted as x, representing the element you need to find the first and last occurrences of x.

Output:

• An array of two integers representing the first and last occurrences of x element in the nums array.

Example 1:

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

Output: [3,4]

Explanation: The output [3, 4] indicates that the target element (8) is found in the array at two positions: first at index 3 and then at index 4. This means the element 8 appears twice in the sorted array, and these indices show its first and last occurrences.

Note:

• The given array is guaranteed to be sorted in ascending order.
• Your solution should have a time complexity better than O(n) to be considered efficient, as a linear search would not be optimal for large arrays. Common efficient approaches include binary search and a combination of binary searches to locate the first and last occurrences of the target element.
• It is possible for the target element to appear multiple times in the array, and you should return the indices corresponding to the first and last occurrences.

The Naive Approach

The naive approach to find the first and last positions of an element in a sorted array involves a simple linear search through the array. Here’s an detailed explanation of this approach:

Algorithm

• Initialize two variables, first and last, to -1. These variables will be used to store the find first and last position of element in sorted array.
• Iterate through the sorted array nums from left to right using a loop or a for loop.
• Inside the loop, check if the current element in nums is equal to the target element. If it is, update the first variable with the current index if first is still -1 (indicating the first occurrence), and update the last variable with the current index (regardless of whether it’s the first or subsequent occurrence).
• Continue the loop until you’ve gone through the entire array.
• After the loop, return the [first, last] pair as the result.

Implementation

Let’s implement the code, in different programming languages.

C Code:

#include <stdio.h>

void searchRange(int nums[], int numsSize, int target, int* result) {
    int first = -1, last = -1;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == target) {
            if (first == -1) {
                first = i;
            }
            last = i;
        }
    }
    
    result[0] = first;
    result[1] = last;
}

int main() {
    int nums[] = {5, 7, 7, 8, 8, 10};
    int target = 8;
    int result[2];

    searchRange(nums, 6, target, result);

    printf("First and Last Positions of %d: [%d, %d]\n", target, result[0], result[1]);
    
    return 0;
}

Output:

First and Last Positions of 8: [3, 4]

Explanation:

• The searchRange function takes four parameters: nums (the sorted array), numsSize (the size of the array), target (the element to search for), and result (an array to store the first and last positions).
• It initializes first and last to -1. These variables will be used to track the first and last positions of the target element in the nums array.
• The function then iterates through the nums array using a for loop, starting from index 0 and going up to numsSize – 1.
• Inside the loop, it checks if the current element (nums[i]) is equal to the target. If it is, it updates first with the current index if first is still -1 (indicating the first occurrence), and it always updates last with the current index to keep track of the last occurrence.
• After the loop, the function stores the first and last values in the result array.
• In the main function, we define the nums array and the target element to search for. We also declare an array result to store the output.
• We call the searchRange function with the provided inputs, and it computes the first and last positions of the target element in the nums array.
• Finally, we print the results to the console.

C++ Code:

#include <iostream>
#include <vector>

using namespace std;

vector<int> searchRange(vector<int>& nums, int target) {
    int first = -1, last = -1;
    
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == target) {
            if (first == -1) {
                first = i;
            }
            last = i;
        }
    }
    
    vector<int> result = {first, last};
    return result;
}

int main() {
    vector<int> nums = {1, 2, 2, 2, 3, 4};
    int target = 3;

    vector<int> result = searchRange(nums, target);

    cout << "First and Last Positions of " << target << ": [" << result[0] << ", " << result[1] << "]" << endl;
    
    return 0;
}

Output:

First and Last Positions of 3: [4, 4]

Explanation:

• This code is very similar to the C code, but it uses vector and cout for input/output.

Java Code:

import java.util.Arrays;

public class FindFirstAndLastPosition {
    public static int[] searchRange(int[] nums, int target) {
        int first = -1, last = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (first == -1) {
                    first = i;
                }
                last = i;
            }
        }

        return new int[]{first, last};
    }

    public static void main(String[] args) {
        int[] nums = {0, 0, 0, 0, 1, 3};
        int target = 2;

        int[] result = searchRange(nums, target);

        System.out.println("First and Last Positions of " + target + ": " + Arrays.toString(result));
    }
}

Output:

First and Last Positions of 2: [-1, -1]

Python Code:

def searchRange(nums, target):
    first = -1
    last = -1
    
    for i in range(len(nums)):
        if nums[i] == target:
            if first == -1:
                first = i
            last = i
    
    return [first, last]

# Example usage:
nums = [5, 7, 7, 8, 8, 10]
target = 8
result = searchRange(nums, target)
print(f"First and Last Positions of {target}: {result}")

Output:

First and Last Positions of 8: [3, 4]

Complexity Analysis:

Time Complexity: The naive approach to find the first and last occurrences of x uses a simple linear search through the array, so its time complexity is O(n), where n is the length of the nums array. In the worst case, it may need to traverse the entire array.

Space Complexity: The algorithm uses a constant amount of extra space to store the first and last variables, so the space complexity is O(1), indicating it’s not dependent on the size of the input array.

Using Binary Search- The Efficient Approach

Algorithm

1. Initialize left and right pointers to 0 and the length of the array minus one(arr.length – 1), respectively.
2. Initialize first and last variables to -1 to track the first and last positions of the target element.
3. While left is less than or equal to right, do the following:
   • Calculate the middle index mid as (left + right)/2.
   • If nums[mid] is equal to the target:
     • Update first to mid if it’s still -1.
     • Update last to mid.
   • If nums[mid] is less than the target, set left to mid + 1.
   • If nums[mid] is greater than the target, set right to mid – 1.
4. After the loop, if first is still -1, return [-1, -1] as the target element was not found in the array.
5. Otherwise, return [first, last], representing the first and last positions of the target element.

Implementation

C Code:

#include <stdio.h>

int findFirst(int nums[], int numsSize, int target) {
    int left = 0, right = numsSize - 1, first = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            first = mid;
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return first;
}

int findLast(int nums[], int numsSize, int target) {
    int left = 0, right = numsSize - 1, last = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            last = mid;
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return last;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int first = findFirst(nums, numsSize, target);
    int last = findLast(nums, numsSize, target);

    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = first;
    result[1] = last;

    *returnSize = 2;
    return result;
}

int main() {
    int nums[] = {1, 1, 1, 1, 1, 1};
    int target = 1;
    int returnSize;

    int* result = searchRange(nums, 6, target, &returnSize);

    printf("First and Last Positions of %d: [%d, %d]\n", target, result[0], result[1]);

    free(result); // Free dynamically allocated memory

    return 0;
}

Output:

First and Last Positions of 1: [0, 5]

Explanation:

• In the findFirst function, we perform a binary search to find the first occurrence of the target element in the nums array. We maintain two pointers, left and right, and update them based on the comparison between nums[mid] and target.
• In the findLast function, we perform a similar binary search to find the last occurrence of the target element.
• The searchRange function calls findFirst and findLast to find the first and last positions of the target element, respectively. It then returns the result as an array.
• In the main function, we provide a sample sorted array nums and a target element target. We call searchRange to find the first and last positions of the target element and print the result.

C++ Code

#include <iostream>
#include <vector>

using namespace std;

int findFirst(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1, first = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            first = mid;
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return first;
}

int findLast(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1, last = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            last = mid;
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return last;
}

vector<int> searchRange(vector<int>& nums, int target) {
    int first = findFirst(nums, target);
    int last = findLast(nums, target);

    return {first, last};
}

int main() {
    vector<int> nums = {-3, -1, 2, 3, 8, 10};
    int target = 3;

    vector<int> result = searchRange(nums, target);

    cout << "First and Last Positions of " << target << ": [" << result[0] << ", " << result[1] << "]" << endl;

    return 0;
}

Output:

First and Last Positions of 3: [3, 3]

Java Code:

import java.util.Arrays;

public class FindFirstAndLastPosition {
    public static int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1, first = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                first = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return first;
    }

    public static int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1, last = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                last = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return last;
    }

    public static int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        int last = findLast(nums, target);

        return new int[]{first, last};
    }

    public static void main(String[] args) {
        int[] nums = {1, 99, 120, 120, 120, 120};
        int target = 120;

        int[] result = searchRange(nums, target);

        System.out.println("First and Last Positions of " + target + ": " + Arrays.toString(result));
    }
}

Output:

First and Last Positions of 120: [2, 5]

Python Code:

def findFirst(nums, target):
    left, right, first = 0, len(nums) - 1, -1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            first = mid
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return first

def findLast(nums, target):
    left, right, last = 0, len(nums) - 1, -1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            last = mid
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return last

def searchRange(nums, target):
    first = findFirst(nums, target)
    last = findLast(nums, target)

    return [first, last]

# Example usage:
nums = []
target = 9
result = searchRange(nums, target)
print(f"First and Last Positions of {target}: {result}")

Output:

First and Last Positions of 9: [-1, -1]

Complexity Analysis

Time Complexity: Both findFirst and findLast perform binary searches, which have a time complexity of O(log n), where n is the length of the nums array. Therefore, the overall time complexity of searchRange is also O(log n).

Space Complexity: The space complexity is O(1) because the algorithm uses a constant amount of extra space for variables, regardless of the size of the input array.

Using the inbuilt Functions

Using built-in functions is another way to find the first and last occurrences of x. You can use functions bisect_left and bisect_right in Python.

Algorithm

• Import the appropriate built-in function for binary search (e.g., bisect_left and bisect_right in Python).
• Use the binary search function to find the index of the first occurrence of the target element. This function typically returns the index where the element should be inserted to maintain the sorted order.
• Use the binary search function again to find the index of the first element that is greater than the target element. This is equivalent to finding the last occurrence of the target element.
• Subtract 1 from the index obtained in step 3 to get the index of the last occurrence of the target element.

Implementation

Python

import bisect

def searchRange(nums, target):
    first = bisect.bisect_left(nums, target)
    last = bisect.bisect(nums, target) - 1

    if first <= last:
        return [first, last]
    else:
        return [-1, -1]

# Example usage:
nums = [1, 1, 2, 2]
target = 2
result = searchRange(nums, target)
print(f"First and Last Positions of {target}: {result}")

Output

First and Last Positions of 8: [2, 3]

Complexity Analysis:

Time Complexity: The built-in binary search functions, such as bisect_left and bisect, typically have a time complexity of O(log n), where n is the length of the array nums. Therefore, the overall time complexity is O(log n).

Space Complexity: The space complexity is O(1) because no additional data structures are used that depend on the size of the input array.

FAQs

Q: What is the purpose of finding the first and last positions of an element in a sorted array?

A: It helps locate all occurrences of a specific element within the array.

Q: How do you find the first occurrence of an element in a sorted array using binary search?

A: Use binary search to find the element, then adjust the right boundary until the first occurrence is found.

Q: How do you find the last occurrence of an element in a sorted array using binary search?

A: Use binary search to find the element, then adjust the left boundary until the last occurrence is found.

Q: What is the time complexity of finding the first and last positions of an element in a sorted array using binary search?

A: The time complexity is O(log n), where n is the length of the array.

Conclusion

• This problem involves locating all occurrences of a target element in a sorted array.
• The binary search approach is a commonly used and efficient method for solving this problem.
• The algorithm finds the first occurrence using one binary search and the last occurrence using another binary search.
• The time complexity of the binary search approach is O(log n), making it efficient for large sorted arrays.
• You can also use built-in functions like bisect in Python to achieve the same result more conveniently.
• The problem is commonly encountered in competitive programming and real-world scenarios when dealing with sorted data.