Tag: MEDIUM

Question 3

Given an array of numbers N and an integer k, your task is to split N into k partitions such that the maximum sum of any partition is minimized. Return this sum.

For example, given N = [5, 1, 2, 7, 3, 4] and k = 3, you should return 8, since the optimal partition is [5, 1, 2], [7], [3, 4].

Approach

  1. Start by sorting the array in descending order. This helps group larger numbers together, making it easier to control the maximum partition sum.
  2. Determine the possible range for the maximum partition sum.
    The lowest possible value is the largest element in the array.
    The highest possible value is the sum of all the elements in the array.
  3. Employ binary search within this range. For each ‘mid’ value:
    a. Try dividing the array into partitions such that no partition sum exceeds ‘mid’.
    b. If you can successfully divide the array, that means ‘mid’ is a possible maximum partition sum. Try to reduce ‘mid’ further (search in the lower half of the range).
    c. If you cannot divide the array, this means ‘mid’ is too small. Explore larger maximum partition sums (search in the upper half of the range).
  4. Continue the binary search until you find the smallest possible ‘mid’ that successfully partitions the array.

Pseudo Code

Code
FUNCTION min_max_partition(nums, k)
   SORT nums in descending order 
   low = largest_number_in(nums)
   high = sum_of_all_elements_in(nums)

   WHILE low < high
       mid = (low + high) / 2 

       IF can_partition(nums, k, mid) 
           high = mid  
       ELSE 
           low = mid + 1

   RETURN low 

FUNCTION can_partition (nums, k, max_allowed_sum)
   current_partition_sum = 0
   num_partitions = 1  

   FOR EACH num IN nums
        IF current_partition_sum + num > max_allowed_sum
            num_partitions = num_partitions + 1 
            current_partition_sum = num  
        ELSE
            current_partition_sum = current_partition_sum + num

   RETURN num_partitions <= k
Explanation
  1. min_max_partition
    • We sort the array for potential optimization.
    • We establish the search space between the largest number and the total sum.
    • The binary search loop iteratively adjusts the low and high boundaries, using the can_partition helper function to evaluate the feasibility of a given mid value as the target maximum partition sum.
  2. can_partition
    • This function tracks the current partition’s sum.
    • If adding a number would exceed the max_allowed_sum, it starts a new partition.
    • It returns True if the array can be divided into ‘k’ or fewer partitions.

Implementation

Golang
package main

import (
	"fmt"
	"sort"
)

func minMaxPartition(nums []int, k int) int {
	// Helper function to check if a partition is possible with a given maximum sum
	canPartition := func(maxSum int) bool {
		subarrays := 0
		currSum := 0
		for _, num := range nums {
			if currSum+num > maxSum {
				subarrays++
				currSum = num // Reset current sum for the new subarray
			} else {
				currSum += num
			}
		}
		return subarrays+1 <= k // Account for the final subarray
	}

	// Sort the array in descending order
	sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] })

	low := nums[0] // Lowest possible maximum sum
	high := 0      // Highest possible maximum sum
	for _, num := range nums {
		high += num
	}

	// Binary search to find the minimum maximum sum
	for low < high {
		mid := low + (high-low)/2
		if canPartition(mid) {
			// Can form partitions using 'mid', try finding a lower maximum sum
			high = mid
		} else {
			// 'mid' is too small, increase the lower bound
			low = mid + 1
		}
	}

	return low
}

func main() {
	nums := []int{5, 1, 2, 7, 3, 4}
	k := 3
	result := minMaxPartition(nums, k)
	fmt.Println(result) // Output: 8
}

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)
}