Tag: UBER

Question 2

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in O(log N) time. You may assume the array does not contain duplicates.

For example, given [5, 7, 10, 3, 4], return 3.

Approach

The core idea is to use a modified binary search. In every iteration, we compare the middle element with the leftmost and rightmost elements. If the middle element is smaller than the rightmost element, the right half is sorted, and the pivot (and the minimum element) must lie in the left half. Conversely, if the middle element is larger than the leftmost element, the left half is sorted, and the pivot is in the right half. In this way, we progressively narrow down the search space until we find the pivot, where the minimum element resides right after it.

Pseudo Code

Code
function findMinimum(nums):
    left = 0
    right = length(nums) - 1

    // Handle arrays with 0 or 1 element
    if right < 0:
        return None // Handle error: Empty array
    if right == 0: 
        return nums[0]

    // Array is already sorted 
    if nums[left] <= nums[right]:
        return nums[left]

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

        // Found the pivot: minimum is the next element
        if nums[mid] > nums[mid + 1]:
            return nums[mid + 1]

        // Left half is sorted    
        if nums[mid] >= nums[left]:
            left = mid + 1
        // Right half is sorted
        else:
            right = mid - 1

    // Should not reach here under normal cases       
    return None
Explanation

Goal: The goal is to find the minimum element in a rotated sorted array within O(log N) time complexity.

Approach: The pseudocode implements a modified binary search approach to achieve this. Here’s how it works:

  1. Initialization: First, it handles edge cases for an empty array or single-element array. Then, it checks if the array is already sorted.
  2. Iterative Narrowing: The code enters a loop and repeatedly calculates the middle element (mid) of the current search space. It then compares this middle element with the leftmost and rightmost elements.
  3. Identifying Pivot: If the middle element is immediately followed by a smaller element, we’ve found the pivot point—the place where the rotation occurred. The minimum element will be the one right after the pivot.
  4. Exploiting Sorted Subarrays: If we haven’t yet found the pivot, the comparisons with the leftmost and rightmost elements tell us which half of the current search space is sorted. This allows us to eliminate either the left or right half from our future search.
  5. Repeat: The process repeats. With each iteration, we reduce the search space by roughly half, leading to logarithmic time complexity.

Implementation

Golang
package main

import "fmt"

func findMin(nums []int) int {
	// Handle edge case of empty array
	if len(nums) == 0 {
		return -1 // Or handle the error appropriately
	}

	left, right := 0, len(nums)-1

	// If array is already sorted (no rotation)
	if nums[left] <= nums[right] {
		return nums[left]
	}

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

		// Check if mid is the pivot point (minimum element)
		if nums[mid] > nums[mid+1] {
			return nums[mid+1]
		}

		// Check which half is sorted to narrow the search
		if nums[mid] >= nums[left] {
			// Left half is sorted, pivot is in the right half
			left = mid + 1
		} else {
			// Right half is sorted, pivot is in the left half
			right = mid - 1
		}
	}

	return -1 // Should not reach here in normal cases
}

func main() {
	arr := []int{5, 7, 10, 3, 4}
	minElement := findMin(arr)
	fmt.Println("Minimum element:", minElement)
}