Skip to content

34.find-first-and-last-position-of-element-in-sorted-array.md

Latest commit

 

History

History
128 lines (111 loc) · 3.55 KB

34.find-first-and-last-position-of-element-in-sorted-array.md

File metadata and controls

128 lines (111 loc) · 3.55 KB

34. Find First and Last Position of Element in Sorted Array

Clarification Questions

  • Does the input array contain duplicates?

Test Cases

Normal Cases

Input: nums = [1,2,3,3,3,4,4,5], target = 3
Output:[2, 4]

Edge / Corner Cases

  • Target does not exist in the array.
Input: nums = [1,2,3,3,3,4,4,5], target = 6
Output: [-1, -1]

Binary Search

For this problem to find the first index of element, we're actually looking for the smallest number >= target, so we can use the same approach to find the smallest number >= target in 35. Search Insert Position.

// First index
target = 7
[..., 7, 7, 7, 7, ...]
      ^
      target <= nums[middle]
      
// Last index
target = 7
 [..., 7, 7, 7, 7, ...]
                ^
nums[middle] <= target

We search the first and last index of search separately by using modified binary search. It stays the same as normal binary search for the cases that not found, i.e. nums[middle] > target or nums[middle] < target.

The key difference is the case of nums[middle] == target, because there might be duplicat, so when we have nums[middle] == target, we don't know if the middle is the first index, and the first index might be at the left part, so we keep searching the left part to find the first index:

target = 7
[..., 7, 7, 7, 7, ...]
 L          M       R
         <--|
 L       R

We keep doing this when nums[middle] == target until breaking the while loop, then left is the first position of target:

[..., 7, 7, 7, 7, ...]
   R  L

Please note that target might not exist in the array, so we have to check if the left is in the range of the array and nums[left] == target. (Applicable to the last index as well)

// findFirstPosition(target = 0)
target = 0
_, 1, 2
   L
   M
R

// findFirstPosition(target = 3)
target = 3
   1, 2, _
         L
      M
      R
fun searchRange(nums: IntArray, target: Int): IntArray {
    return intArrayOf(
        findFirstPosition(nums, target),
        findLastPosition(nums, target)
    )
}

private fun findFirstPosition(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (target <= nums[middle]) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return if (left in 0 until nums.size && nums[left] == target) left else -1
}

// Or equivalently, and same idea for findLastPosition()
private fun findFirstPosition(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    var result = -1
    while (left <= right) {
        val middle = left + (right - left) / 2
        // We update the index if we found the target.
        if (nums[middle] == target) result = middle

        if (target <= nums[middle]) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return result
}

private fun findLastPosition(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (nums[middle] <= target) {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return if (right in 0 until nums.size && nums[right] == target) right else -1
}
  • Time Complexity: O(log n) for binary search.
  • Space Complexity: O(1).