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

Spoiler alert—this paragraph contains the answer.

Problem Statement

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.

Approach

I didn't notice the O(log n) requirement at first, so I used a simple two-pointer method on the sorted array.

1. Initialize two pointers: left = 0,right = len(nums) - 1. Our goal is to find the first and last indices of target.
2. Move left forward while nums[left] < target, and move right backward while nums[right] > target to shrink the range.
3. When nums[left] == target or nums[right] == target, record the candidate first/last positions.
4. Return [first, last] if found; otherwise return [-1, -1].

NOTE This method is not O(log n) but O(n) in the worst case!

Better Approach (Binary Search)

1. Use binary search on the sorted array. Compute m = (left + right) // 2 and compare nums[m] with target.
2. Decide which bound you're looking for: lower bound (first index) or upper bound (last index).
3. By the time we find nums[m] == target. Now we have find the two boundaries.

[......,7 ,7, 7, 7,........]
				 Δ        Δ
				 |        |
		   lower    upper

1. For the lower bound:
2. • If we alread assume nums[m] == target so next we need to consider whether it is the boundary.
   • If m == left or nums[m - 1] < target, we found the first index (m).
   • Otherwise, move right = m - 1.
2. For the upper bound:

• • If m == right or nums[m + 1] > target, we found the last index (m). Otherwise, move left = m + 1 and keep searching.

And we need to deal with when num[m] != target

• • If nums[m] < target, move left = m + 1.
  • If nums[m] > target, move right = m - 1.

Continue until left > right. If we never meet the boundary condition, the target doesn't exist.

What can I use this in our life?

Recently I’ve been playing Candy Crush. You match three or more candies in a row or column. Suppose we have five types of candy labeled 1–5, and the board is:

[1, 2, 5, 4, 5, 1, 5, 5, 2, 3, 4, 1, 2, 5, 1, 5]

With one adjacent swap, the goal is to create the longest possible line so you can trigger a stronger effect. After imagining a swap, just check that row or column and read off the first and last index of the same candy to measure the line length.