Find First and Last Position of Element

📋

Find First and Last Position of Element

Edge cases:

</>

IDE

def searchRange(nums: list[int], target: int) -> list[int]:public int[] searchRange(int[] nums, int target)vector<int> searchRange(vector<int>& nums, int target)function searchRange(nums, target)

def searchRange(nums, target):
    # Write your solution here
    pass

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // Write your solution here
        return new int[]{-1, -1};
    }
}

#include <vector>
using namespace std;

vector<int> searchRange(vector<int>& nums, int target) {
    // Write your solution here
    return {-1, -1};
}

function searchRange(nums, target) {
    // Write your solution here
    return [-1, -1];
}

Common Bugs to Avoid

Wrong: [-1, -1] when target is presentBinary search fails to find target due to incorrect mid calculation or loop conditions.✅ Ensure mid is calculated as mid = low + (high - low) // 2 and update low/high pointers correctly.

Wrong: [index, index] where index is any occurrence but not leftmost or rightmostBinary search returns any occurrence instead of leftmost or rightmost boundary.✅ Modify binary search to continue searching left half when finding target for left boundary and right half for right boundary.

Wrong: Indices out of range or crashes on empty inputNo check for empty array before binary search.✅ Add base case to return [-1, -1] if nums is empty.

Wrong: Timeout on large inputUsing linear scan instead of binary search.✅ Implement O(log n) binary search to find boundaries.

Wrong: Incorrect boundaries when all elements are targetBinary search stops at first found target instead of searching full range.✅ Continue binary search after finding target to find true leftmost and rightmost indices.

✓

Test Cases

Try testing your solution on empty and single-element arrays to catch base cases.

Consider edge cases where target is outside the range of array elements or appears multiple times.

Optimize your solution to use binary search to handle large inputs efficiently.

t1_01basic

Input{"nums":[5,7,7,8,8,10],"target":8}

Expected[3,4]

⏱ Performance - must finish in 2000ms

The target 8 appears first at index 3 and last at index 4.

💡 Think about how binary search can be modified to find boundaries.

💡 Use two binary searches: one for the leftmost and one for the rightmost occurrence.

💡 Implement binary search to find the first index where nums[i] == target and similarly for the last index.

Why it failed: Returned wrong indices; likely binary search did not correctly find leftmost or rightmost occurrence. Fix by ensuring binary search moves left when target found for left boundary and moves right for right boundary.

✓ Correctly finds first and last positions using modified binary search.

t1_02basic

Input{"nums":[1,2,3,4,5,6,7,8,9],"target":5}

Expected[4,4]

⏱ Performance - must finish in 2000ms

Target 5 appears only once at index 4.

💡 Check how binary search behaves when target appears once.

💡 Ensure your search returns the same index for both first and last occurrence when only one instance exists.

💡 Use the same binary search logic for both boundaries but confirm indices match when target is unique.

Why it failed: Incorrect range returned for single occurrence; possibly binary search boundaries not handled properly. Fix by verifying binary search returns same index for both searches when target is unique.

✓ Correctly handles single occurrence target.

t2_01edge

Input{"nums":[],"target":3}

Expected[-1,-1]

⏱ Performance - must finish in 2000ms

Empty array should return [-1, -1] since target cannot be found.

💡 Consider what happens when the input array is empty.

💡 Your code should handle n=0 without errors and return [-1, -1].

💡 Add a base case to return [-1, -1] immediately if nums is empty.

Why it failed: Code crashes or returns invalid indices on empty input. Fix by adding a check for empty array and returning [-1, -1] immediately.

✓ Handles empty input gracefully.

t2_02edge

Input{"nums":[7],"target":7}

Expected[0,0]

⏱ Performance - must finish in 2000ms

Single element array where element equals target; both first and last positions are 0.

💡 Test behavior when array has only one element.

💡 Binary search should return index 0 for both first and last occurrence if that element matches target.

💡 Ensure binary search handles single-element arrays correctly without infinite loops.

Why it failed: Fails to return correct indices for single-element array; possibly binary search loop conditions incorrect. Fix by adjusting loop conditions to handle single-element arrays.

✓ Correctly handles single-element arrays.

t2_03edge

Input{"nums":[2,2,2,2,2],"target":2}

Expected[0,4]

⏱ Performance - must finish in 2000ms

All elements equal to target; first index is 0 and last index is 4.

💡 Consider when all elements are the target.

💡 Binary search for left boundary should find index 0, right boundary index n-1.

💡 Make sure your binary search does not stop at first found target but continues to find boundaries.

Why it failed: Returns incorrect boundaries when all elements are target; likely binary search stops early. Fix by continuing search after finding target to find true boundaries.

✓ Correctly finds boundaries when all elements match target.

t2_04edge

Input{"nums":[1,2,3,4,5],"target":6}

Expected[-1,-1]

⏱ Performance - must finish in 2000ms

Target larger than all elements; should return [-1, -1].

💡 Check how your binary search handles targets larger than all elements.

💡 Ensure binary search returns -1 when target not found, not an incorrect index.

💡 Verify boundary conditions to avoid returning indices out of range.

Why it failed: Returns invalid indices instead of [-1, -1] when target is larger than all elements. Fix by checking if found index actually matches target before returning.

✓ Correctly returns [-1, -1] for target larger than all elements.

t3_01corner

Input{"nums":[1,2,3,4,5,6,7,8,9],"target":10}

Expected[-1,-1]

⏱ Performance - must finish in 2000ms

Target larger than all elements; should return [-1, -1].

💡 Check how your binary search handles targets larger than all elements.

💡 Ensure binary search returns -1 when target not found, not an incorrect index.

💡 Verify boundary conditions to avoid returning indices out of range.

Why it failed: Returns invalid indices instead of [-1, -1] when target is larger than all elements. Fix by checking if found index actually matches target before returning.

✓ Correctly returns [-1, -1] for target larger than all elements.

t3_02corner

Input{"nums":[1,2,3,4,5,6,7,8,9],"target":0}

Expected[-1,-1]

⏱ Performance - must finish in 2000ms

Target smaller than all elements; should return [-1, -1].

💡 Check how your binary search handles targets smaller than all elements.

💡 Ensure binary search returns -1 when target not found, not an incorrect index.

💡 Verify boundary conditions to avoid returning indices out of range.

Why it failed: Returns invalid indices instead of [-1, -1] when target is smaller than all elements. Fix by checking if found index actually matches target before returning.

✓ Correctly returns [-1, -1] for target smaller than all elements.

t3_03corner

Input{"nums":[1,2,2,2,3,4,5],"target":2}

Expected[1,3]

⏱ Performance - must finish in 2000ms

Multiple occurrences of target in middle; first at index 1, last at index 3.

💡 Beware of off-by-one errors when updating mid and boundaries.

💡 Make sure left boundary binary search moves right pointer correctly when target found.

💡 Make sure right boundary binary search moves left pointer correctly when target found.

Why it failed: Off-by-one error causes incorrect boundaries for multiple occurrences. Fix by carefully updating low/high pointers in binary search loops.

✓ Correctly finds boundaries with multiple occurrences.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100000],"target":99999}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100000; solution must run in O(log n) time within 2 seconds.

💡 Linear scan will time out on large inputs.

💡 Use binary search to achieve O(log n) time complexity.

💡 Implement two binary searches to find leftmost and rightmost indices efficiently.

Why it failed: Solution times out due to O(n) linear scan. Fix by implementing O(log n) binary search approach.

✓ Solution runs within time limits using O(log n) binary search.

Practice

1. Consider the following Python code implementing the min-heap approach to find the kth smallest element in a sorted matrix. Given the matrix [[1,3],[2,4]] and k = 3, what value does the function return?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Initialize min-heap with first elements

   Push (1,0,0) and (2,1,0) into heap.

2. Step 2: Extract elements until count == k

   Pop 1 (count=1), push 3 from row 0; pop 2 (count=2), push 4 from row 1; pop 3 (count=3), return 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Third smallest element is 3 [OK]

Hint: Trace heap pops and pushes carefully [OK]

Common Mistakes:

• Off-by-one counting of popped elements
• Returning wrong popped value
• Confusing row and column indices

2. Consider the following code snippet that searches for a target in a 2D matrix by performing binary search on each row. Given the matrix = [[1,3,5],[7,9,11],[13,15,17]] and target = 9, what is the return value of the function searchMatrix(matrix, target)?

easy

A. True

B. Returns None

C. Raises an exception

D. False

Solution

1. Step 1: Trace binary search on second row [7,9,11]

   Mid index 1 has value 9 which equals target, so binary_search returns True.

2. Step 2: searchMatrix returns True immediately after finding target

   Since binary_search returns True for second row, searchMatrix returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Target found in second row at mid index 1 [OK]

Hint: Binary search returns True when target found [OK]

Common Mistakes:

• Off-by-one errors in mid calculation
• Returning False prematurely
• Confusing return values

3. What is the time complexity of the optimal binary search algorithm that finds the single non-duplicate element in a sorted array where every other element appears twice?

medium

A. O(n) because each element is checked at least once

B. O(log n) because the search space halves each iteration based on parity checks

C. O(n log n) due to repeated comparisons and index parity calculations

D. O(1) since only a few elements are compared at each step

Solution

1. Step 1: Identify loop behavior

   The while loop halves the search space each iteration by adjusting low or high based on parity comparisons.

2. Step 2: Confirm complexity

   Halving search space each iteration leads to O(log n) time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search is classic O(log n) [OK]

Hint: Halving search space -> logarithmic time [OK]

Common Mistakes:

• Confusing linear scan with binary search
• Assuming parity checks add extra complexity
• Misreading O(1) as possible for search

4. What is the time complexity of the Newton's method approach for computing the integer square root of a number x?

medium

A. O(log log x)

B. O(√x)

C. O(x)

D. O(log x)

Solution

1. Step 1: Understand Newton's method convergence

   Newton's method converges quadratically, roughly doubling correct digits each iteration.

2. Step 2: Analyze iteration count relative to input size

   Because of quadratic convergence, the number of iterations is proportional to log log x, making time complexity O(log log x).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Newton's method converges faster than logarithmic time [OK]

Hint: Newton's method converges quadratically -> O(log log x) [OK]

Common Mistakes:

• Confusing with brute force O(√x)
• Assuming linear O(x) complexity
• Mistaking logarithmic O(log x)

5. Suppose the array is no longer sorted and may contain duplicates, and you still need to count occurrences of a target efficiently. Which approach is best suited to handle this scenario?

hard

A. Use binary search on the unsorted array to find boundaries

B. Sort the array first, then use binary search to count occurrences

C. Use a hash map to count occurrences in a single pass

D. Use a greedy approach to skip duplicates and count

Solution

1. Step 1: Recognize unsorted array limitation

   Binary search requires sorted data; it cannot be applied directly here.

2. Step 2: Evaluate alternatives

   Sorting first adds O(n log n) overhead; hash map counting is O(n) and direct.

3. Step 3: Choose hash map approach

   Hash map counts occurrences in one pass with O(n) time and O(n) space, optimal for unsorted arrays.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Hash map counting works regardless of order [OK]

Hint: Unsorted array -> hash map counting [OK]

Common Mistakes:

• Trying binary search on unsorted data
• Sorting then binary searching is slower
• Greedy skipping duplicates misses counts