Find First and Last Position of Element in Sorted Array Solution | Code in C++/Java/Python/JS
Problem Description:
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.
Examples:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]
Explanation: The first position of 8 is at index 3, and the last position is at index 4.
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1, -1]
Explanation: There's not even a single occurrence of 6 in the array hence, return -1, -1.
Input: nums = [], target = 0
Output: [-1, -1]
Explanation: There's not even a single occurrence of 0 in the array hence return -1, -1.
Constraints:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums is a non-decreasing array.
- -109 <= target <= 109
Find First and Last Position of Element in Sorted Array Problem
Given a sorted array, our task is to determine the index of the first and last occurrence of a specified target value within the array. If the target value appears multiple times, we need to return the indices of its first and last positions. If the target is not present in the array, we should return [-1, -1].
For now, we are not concerned with optimizing the solution to achieve a time complexity of O(log n). Instead, our primary goal is to focus on implementing a correct and straightforward solution, ensuring that it works as expected.
Brute Force Approach
Intuition:
How will your thinking go once you understand this problem? You see that we need to return the indexes of the first and last occurrences of the target. So, let's go through each index of nums and check if the value at that index is equal to the target. Intuitive right?
Find First and Last Position of Element in Sorted Array Solution
To keep track of the first and last occurrences, we maintain two variables:
- One to store the first occurrence of the target.
- Another is to store the last occurrence of the target.
We initialize both the variables to -1. This helps us verify whether the target was found in the array. If these variables remain -1 after iterating through the array, it means the target does not exist in the array, and we can simply return [-1, -1].
Now, while iterating assume we land on an index where the value is equal to the target. If this happens the first time then we know that this index is the first occurrence and may be the last occurrence where the target is.
Hence, the first time the target appears we mark it as both the first and the last occurrence.
Why do we mark the index as both first and last occurrence?
For example, if the target number is 5 and it first appears at position 3 in the list, we say:
- First occurrence is at position 3.
- Last occurrence is also at position 3.
As we continue to go through the list, if we find the target number again at a different position, we only update the last occurrence to this new position. The first occurrence remains unchanged.
For instance, if we find the number 5 again at position 7, we update the last occurrence to position 7, but the first occurrence stays at position 3:
- First occurrence is still at position 3.
- Last occurrence is now at position 7.
This way, by the end of scanning the list, we know the very first place we found the target and the most recent place we found it. The first occurrence doesn't change after it's set, while the last occurrence is updated each time we find the target again.
Once we are done iterating we return the values stored in the variables denoting first and last occurrences.
Dry run
Input: nums = [-5, -4, -1, 2, 2, 4], target = 2
Output: [3, 4]
Explanation: The first position of 2 is at index 3 and the last position is at index 4.
Initial Setup:
- nums = [-5, -4, -1, 2, 2, 4]
- target = 2
- n = nums.size() = 6
- start = -1
- last = -1
Iterating over nums with a for loop:
Iteration 1 (i = 0):
- nums[0] = -5
- nums[0] != target (2)
- No changes to start or last.
Iteration 2 (i = 1):
- nums[1] = -4
- nums[1] != target (2)
- No changes to start or last.
Iteration 3 (i = 2):
- nums[2] = -1
- nums[2] != target (2)
- No changes to start or last.
Iteration 4 (i = 3):
- nums[3] = 2
- nums[3] == target (2)
- Since start == -1, start is set to i = 3.
- last is updated to i = 3.
Iteration 5 (i = 4):
- nums[4] = 2
- nums[4] == target (2)
- start remains 3 (it was already set).
- last is updated to i = 4.
Iteration 6 (i = 5):
- nums[5] = 4
- nums[5] != target (2)
- No changes to start or last.
Final Values:
- start = 3
- last = 4
Output:
- The function returns {start, last} which is {3, 4}.
Steps to write code
Step 1: Initialize Variables
- Initialize the size of the array n.
- Set two variables start and last to -1. These will store the indices of the first and last occurrences of the target.
Step 2: Iterate Over the Array
- Use a for loop to traverse through each element of the array.
- If the current element equals target:
- First occurrence: If start is -1, this is the first time we encounter the target, so we set start to the current index.
- Last occurrence: Regardless of whether it's the first occurrence or not, we keep updating last with the current index.
Step 3: Return the Result
- After completing the loop, return a vector containing start and last. If no occurrences of the target were found, both values will remain -1.
Find First and Last Position of Element in Sorted Array solution
Find First and Last Position of Element in Sorted Array solution in c++
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// Get the size of the array
int n = nums.size();
// Initialize variables to store first and last occurrence
int start = -1, last = -1;
// Traverse the array to find the first and last occurrence of the target
for(int i = 0; i < n; ++i) {
if(nums[i] == target) {
// If this is the first occurrence, store it
if(start == -1) start = i;
// Update last occurrence every time we find the target
last = i;
}
}
// Return the first and last index of the target
return {start, last};
}
};Find First and Last Position of Element in Sorted Array solution in java
class Solution {
public int[] searchRange(int[] nums, int target) {
// Get the size of the array
int n = nums.length;
// Initialize variables to store first and last occurrence
int start = -1, last = -1;
// Traverse the array to find the first and last occurrence of the target
for (int i = 0; i < n; i++) {
if (nums[i] == target) {
// If this is the first occurrence, store it
if (start == -1) start = i;
// Update last occurrence every time we find the target
last = i;
}
}
// Return the first and last index of the target
return new int[]{start, last};
}
}Find First and Last Position of Element in Sorted Array solution in python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# Get the size of the array
n = len(nums)
# Initialize variables to store first and last occurrence
start, last = -1, -1
# Traverse the array to find the first and last occurrence of the target
for i in range(n):
if nums[i] == target:
# If this is the first occurrence, store it
if start == -1:
start = i
# Update last occurrence every time we find the target
last = i
# Return the first and last index of the target
return [start, last]Find First and Last Position of Element in Sorted Array solution in javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
// Get the size of the array
let n = nums.length;
// Initialize variables to store first and last occurrence
let start = -1, last = -1;
// Traverse the array to find the first and last occurrence of the target
for (let i = 0; i < n; i++) {
if (nums[i] === target) {
// If this is the first occurrence, store it
if (start === -1) start = i;
// Update last occurrence every time we find the target
last = i;
}
}
// Return the first and last index of the target
return [start, last];
};Find First and Last Position of Element in Sorted Array Complexity Analysis
Time Complexity: O(n)
The code iterates over the entire array once using a single for loop. Let’s analyze the operations inside the loop:
Loop Iteration:
- The loop runs n times, where n is the length of the input array nums.
- On each iteration, we perform a constant-time check (nums[i] == target), and if true, we perform a constant-time assignment to the start and last variables.
- Hence, loop iteration takes O(n).
Overall Operations:
- The loop runs once for each element in the array, and each operation inside the loop (comparison and assignment) takes constant time, i.e., O(1).
Thus, the time complexity of the loop is O(n) where n is the length of the input array nums.
Final Time Complexity:
- The time complexity of the entire code is O(n).
Space Complexity: O(1)
Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm excluding the space used by the input.
- The only extra variables used in this code are start, last, and n:
- start and last are scalar variables (integers) used to store the first and last occurrence of the target.
- n stores the size of the nums array.
- These variables take up constant space, O(1), because they do not depend on the size of the input.
So, the auxiliary space complexity is O(1).
Total Space Complexity
Total space refers to the overall memory used by the algorithm, including the input space and any additional space.
- The input space is the nums array, which is of size n. Thus, the space used by the input is O(n).
- The code only uses a few extra variables (as mentioned above), which contributes O(1) space.
So, the total space complexity is the sum of the input space O(n) and the auxiliary space O(1), which gives:
- Total space complexity: O(n)
Is the brute force approach efficient?
For n <= 105, our solution has a time complexity of O(n), which comfortably meets the given constraints. This falls well within the time limits of most competitive programming environments, which typically allow around 1-2 seconds for execution.
Thus, the O(n) time complexity is optimal and works efficiently even with large input sizes like n = 10 ⁴, ensuring the solution runs within the acceptable time frame without risking a Time Limit Exceeded (TLE) error.
But we are asked to write an algorithm with O(logn) Complexity.
How to do this? Let's see...
Optimal Approach
Intuition:
To optimize the solution, we cannot afford to check every index of the array one by one, as we did in the brute force approach. That method takes O(n) time, which is not efficient for very large inputs.
Instead, we need to take a smarter approach to locate the first and last occurrence of the target value more efficiently. Rather than scanning through the entire array, we should find a way to quickly narrow down the positions where the target might appear.
This means focusing only on the parts of the array where the target could be, rather than checking every single element.
This is possible because the given array is sorted. This means if we pick any element, we can immediately tell whether the number we’re looking for will be to the left (smaller numbers) or the right (larger numbers).
First, let's focus on finding the first occurrence of the target in the array nums.
We start by picking some index i in the array. Now, if the value at index i is equal to the target or greater than the target, it means that the first occurrence of the target must be at index i or somewhere before it. Hence, we now can ignore the right part and look at the left part.
On the other hand, if the value at index i is smaller than the target, it means the first occurrence must be somewhere after i, so we should move towards the right side of the array.
This way, we can systematically decide whether to look to the left of i or to the right based on the value at index i.
To make this process more efficient, we choose i as the middle element of the remaining portion of the array. By doing this, we can eliminate either the left half or the right half in each step, effectively cutting down the number of elements we need to check.
After eliminating one half, we repeat the same approach on the remaining portion of the array, further reducing the number of elements to search. We continue this process until we are left with only one element, at which point we either find the target or determine that it doesn’t exist in the array.
This approach of dividing the search space in half is called binary search. Want to know more? Refer to the link below.
Now it should be easy for you to apply the same approach to find the last occurrence of the target. Let's see what we will do in this case quickly.
To find the last occurrence of the target in the array, we follow a similar approach to finding the first occurrence.
Find First and Last Position of Element in Sorted Array Algorithm
We start by setting up two pointers, low and high:
- low is initially placed at the beginning of the array (index 0).
- high is placed at the end of the array (index n-1).
These two pointers help us define the range in which we will search for the last occurrence of the target.
Next, we repeatedly choose the middle element of the current range as our reference point. This middle element helps us decide whether we need to search towards the left or the right.
If the value at mid is greater than the target, this means the target (if it exists) must be somewhere to the left. So, we move high to mid - 1 and continue searching in the left half.
If the value at mid is equal to the target, this means we have found an occurrence of the target. But since we are looking for the last occurrence, we need to check further towards the right to see if the target appears again. So, we update our answer to mid and move low to mid + 1 to continue searching in the right half.
The difference between finding the first and last occurrence of a target in a list lies in how we handle the situation when we find the target at the mid-point. When searching for the first occurrence, if the value at mid is equal to the target, we then search to the left, hoping to find an earlier occurrence of the target. On the other hand, when searching for the last occurrence, if the value at mid is equal to the target, we search to the right, hoping to find a later occurrence of the target
If the value at mid is less than the target, this means the target (if present) must be somewhere to the right. So, we move low to mid + 1 and continue searching in the right half.
We keep repeating this process until low and high converge, ensuring that we have found the last occurrence of the target in the array.
A similar good problem highly recommended is search element in sorted rotated array. Do check that!.
Find First and Last Position of Element in Sorted Array-Optimal Animation Explaination
Dry run
Input: nums = [-5, -4, -1, 2, 2, 4], target = 2
Output: [3, 4]
Explanation: The first position of 2 is at index 3 and the last position is at index 4.
Initialize Variables
- n = 6 (size of the array)
- res = [-1, -1] (default values)
- low = 0, high = 5 (searching in the full array)
Finding the First Occurrence of target = 2 Iteration 1
- mid = (0 + 5) / 2 = 2
- nums[2] = -1, which is less than target, so move right.
- Update low = mid + 1 = 3
Iteration 2
- mid = (3 + 5) / 2 = 4
- nums[4] = 2, which equals target, so update res[0] = 4 (first occurrence found but might be earlier).
- Move left (high = mid - 1 = 3) to find an earlier occurrence.
Iteration 3
- mid = (3 + 3) / 2 = 3
- nums[3] = 2, which equals target, so update res[0] = 3 (earlier occurrence found).
- Move left (high = mid - 1 = 2), but now low > high, so stop.
First occurrence found at index = 3
res = [3, -1]
Finding the Last Occurrence of target = 2
- Reset low = 0, high = 5 (searching in full array again)
Iteration 1
- mid = (0 + 5) / 2 = 2
- nums[2] = -1, which is less than target, so move right.
- Update low = mid + 1 = 3
Iteration 2
- mid = (3 + 5) / 2 = 4
- nums[4] = 2, which equals target, so update res[1] = 4 (last occurrence found but might be later).
- Move right (low = mid + 1 = 5) to check further.
Iteration 3
- mid = (5 + 5) / 2 = 5
- nums[5] = 4, which is greater than target, so move left.
- Update high = mid - 1 = 4, but now low > high, so stop.
Last occurrence found at index = 4
res = [3, 4]
Steps to write code
Step 1: Initialize variables
- Get the size of the array (n).
- Create a result vector res of size 2 and initialize both elements to -1 (res = [-1, -1]).
- Set two pointers low = 0 and high = n - 1.
Step 2: Find the First Occurrence of target
- Use binary search to find the first occurrence.
- While low <= high:
- Compute mid = (low + high) / 2.
- If nums[mid] is greater than or equal to target:
- If nums[mid] == target, update res[0] = mid.
- Move left (high = mid - 1) to find an earlier occurrence.
- Else, move right (low = mid + 1).
Step 3: Reset low and high for the next search
- Set low = 0 and high = n - 1 again.
Step 4: Find the Last Occurrence of target
- Use binary search to find the last occurrence.
- While low <= high:
- Compute mid = (low + high) / 2.
- If nums[mid] is less than or equal to target:
- If nums[mid] == target, update res[1] = mid.
- Move right (low = mid + 1) to find a later occurrence.
- Else, move left (high = mid - 1).
Step 5: Return the result
- The result res now contains [first occurrence index, last occurrence index].
- If the target is not found, both values in res remain -1.
Find First and Last Position of Element in Sorted Array leetcode solution
Find First and Last Position of Element in Sorted Array solution in c++
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// Get the size of the array
int n = nums.size();
// Initialize result vector with -1 (default value if target is not found)
vector<int> res(2, -1);
// Initialize two pointers for binary search
int low = 0, high = n - 1;
// Finding the first occurrence of the target
while (low <= high) {
// Calculate the middle index
int mid = (low + high) / 2;
// If mid is greater than or equal to target, move left
if (nums[mid] >= target) {
// If we found the target, update first occurrence
if (nums[mid] == target) {
res[0] = mid;
}
// Move towards the left
high = mid - 1;
} else {
// Move towards the right
low = mid + 1;
}
}
// Reset low and high for finding last occurrence
low = 0, high = n - 1;
// Finding the last occurrence of the target
while (low <= high) {
// Calculate the middle index
int mid = (low + high) / 2;
// If mid is less than or equal to target, move right
if (nums[mid] <= target) {
// If we found the target, update last occurrence
if (nums[mid] == target) {
res[1] = mid;
}
// Move towards the right
low = mid + 1;
} else {
// Move towards the left
high = mid - 1;
}
}
// Return the first and last occurrence indices
return res;
}
};Find First and Last Position of Element in Sorted Array solution in java
class Solution {
public int[] searchRange(int[] nums, int target) {
// Get the size of the array
int n = nums.length;
// Initialize result array with -1 (default value if target is not found)
int[] res = new int[2];
res[0] = -1; // First occurrence
res[1] = -1; // Last occurrence
// Initialize two pointers for binary search
int low = 0, high = n - 1;
// Finding the first occurrence of the target
while (low <= high) {
// Calculate the middle index
int mid = (low + high) / 2;
// If mid is greater than or equal to target, move left
if (nums[mid] >= target) {
// If we found the target, update first occurrence
if (nums[mid] == target) {
res[0] = mid;
}
high = mid - 1; // Move towards the left
} else {
low = mid + 1; // Move towards the right
}
}
// Reset low and high for finding last occurrence
low = 0;
high = n - 1;
// Finding the last occurrence of the target
while (low <= high) {
// Calculate the middle index
int mid = (low + high) / 2;
// If mid is less than or equal to target, move right
if (nums[mid] <= target) {
// If we found the target, update last occurrence
if (nums[mid] == target) {
res[1] = mid;
}
low = mid + 1; // Move towards the right
} else {
high = mid - 1; // Move towards the left
}
}
// Return the first and last occurrence indices
return res;
}
}Find First and Last Position of Element in Sorted Array solution in python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# Get the size of the array
n = len(nums)
# Initialize result array with -1 (default value if target is not found)
res = [-1, -1]
# Initialize two pointers for binary search
low, high = 0, n - 1
# Finding the first occurrence of the target
while low <= high:
mid = (low + high) // 2
# If mid is greater than or equal to target, move left
if nums[mid] >= target:
# If we found the target, update first occurrence
if nums[mid] == target:
res[0] = mid
high = mid - 1 # Move towards the left
else:
low = mid + 1 # Move towards the right
# Reset low and high for finding last occurrence
low, high = 0, n - 1
# Finding the last occurrence of the target
while low <= high:
mid = (low + high) // 2
# If mid is less than or equal to target, move right
if nums[mid] <= target:
# If we found the target, update last occurrence
if nums[mid] == target:
res[1] = mid
low = mid + 1 # Move towards the right
else:
high = mid - 1 # Move towards the left
# Return the first and last occurrence indices
return resFind First and Last Position of Element in Sorted Array solution in javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
let n = nums.length;
let res = [-1, -1]; // Initialize result array with -1 (default value if target is not found)
let low = 0, high = n - 1;
// Finding the first occurrence of the target
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (nums[mid] >= target) {
if (nums[mid] === target) {
res[0] = mid; // Update first occurrence
}
high = mid - 1; // Move towards the left
} else {
low = mid + 1; // Move towards the right
}
}
// Reset low and high for finding last occurrence
low = 0;
high = n - 1;
// Finding the last occurrence of the target
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (nums[mid] <= target) {
if (nums[mid] === target) {
res[1] = mid; // Update last occurrence
}
low = mid + 1; // Move towards the right
} else {
high = mid - 1; // Move towards the left
}
}
return res;
};Find First and Last Position of Element in Sorted Array Complexity Analysis
Time Complexity: O(log n)
Initialization:
- Getting the size of the array: O(1)
- Initializing the result vector: O(1)
- Initializing low and high: O(1)
- Total for initialization: O(1)
Finding the First Occurrence (Binary Search #1)
- This is a binary search, and in each iteration, the search space is reduced by half.
Binary search works by repeatedly dividing the search range in half until the correct index is found.
Breaking It Down
- At the beginning: The search space has n elements.
- After 1st iteration: The search space is reduced to n/2.
- After 2nd iteration: The search space is n/4.
- After k iterations: The search space becomes n / 2k.
The search ends when only one element remains, which happens when: n/2k = 1
Taking log base 2 on both sides: k=log2(n)
Thus, binary search runs in O(log n) time complexity.
Reset low and high for Second Search
- This is just a variable assignment.
- Time Complexity: O(1)
Finding the Last Occurrence (Binary Search #2)
- Again, this is a binary search, reducing the search space by half in each iteration.
- Time Complexity: O(log N)
Returning the Result
- Returning a vector takes O(1) time.
- Time Complexity: O(1)
Hence, the overall time complexity is: O(logn)
Space Complexity: O(1)
Auxiliary Space Complexity
Auxiliary space complexity refers to the extra memory used by the algorithm, excluding the memory used by the input.
- Result Vector (res):
This is a fixed-size vector of size 2 used to store the first and last indices of the target. It takes O(1) space. - Temporary Variables (low, high, mid):
These are simple scalar variables used during the binary search. Each of them takes O(1) space.
Since there are no additional data structures that grow with the input size, the auxiliary space complexity is: O(1)
Total Space Complexity
Total space complexity considers the total memory used by the algorithm, including both the input and any additional space used during the execution.
- Input Size (nums):
The input array nums of size n is given as input. It consumes O(n) space. - Auxiliary Space as we have seen is O(1)
Thus, the total space complexity is: O(n)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.
You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti...righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.
- For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|*". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.
Return an integer array answer where answer[i] is the answer to the ith query.
You are given a 0-indexed integer array nums and a target element target.
A target index is an index i such that nums[i] == target.
Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.