Category: Daily Question

This category is for daily questions practice

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

Question 1

Given the head of a singly linked list, swap every two nodes and return its head.

Approach

In the realm of linked lists, a classic algorithmic puzzle is to rearrange the structure by swapping adjacent pairs of nodes. Your task is to develop a solution that elegantly modifies the links within a given linked list to achieve this pairwise swap.

Pseudo Code

Code
function swapPairs(head)
  //  Handle base cases: empty list or single node
  if head == NULL or head.next == NULL
    return head

  // Create pointers to track nodes:
  // 'prev' will point to the node before the pair to swap  
  // 'curr' will point to the first node of the pair  
  // 'next' will point to the second node of the pair
  prev = NULL
  curr = head
  next = head.next

  // Iterate through the list:  
  while curr != NULL and next != NULL
      // Set prev.next to the second node, effectively reversing the first pair
      if prev != NULL 
          prev.next = next 
      else
          head = next // Update 'head' for the first pair swap

      // Perform the swap
      curr.next = next.next
      next.next = curr 

      // Move pointers to prepare for the next swap
      prev = curr
      curr = curr.next 
      next = curr.next if curr != NULL 

  return head
Explanation
  1. Base Cases: Check if the list is empty (head == NULL) or if it has only one node (head.next == NULL). In these cases, no swapping is needed, so you directly return the head.
  2. Pointers:
    • prev: Keeps track of the node before the current pair to update its next pointer.
    • curr: Points to the first node of the current pair to be swapped.
    • next: Points to the second node of the current pair.
  3. Iteration: The while loop iterates until you’ve processed all pairs.
  4. Reversing the Pair:
    • If prev is not NULL (it won’t be for the first pair), you set prev.next to next, effectively reversing the direction of the first two nodes.
    • If prev is NULL, this is the first pair in the list so you update the head pointer to next.
  5. Swapping:
    • curr.next is set to next.next (the node after the pair).
    • next.next is set to curr (completing the swap).
  6. Update Pointers:
    • Update prev, curr, and next to prepare for the next pair swap.

Implementation

Golang
package main

import "fmt"

// Node represents a node in the singly linked list
type Node struct {
    Val  int
    Next *Node
}

// Function to swap pairs in the linked list
func swapPairs(head *Node) *Node {
    // Base cases: empty list or single node
    if head == nil || head.Next == nil {
        return head
    }

    // Create dummy head (simplifies initial swap)
    dummy := &Node{Next: head}
    prev := dummy
    curr := head
    next := head.Next

    // Iterate and swap pairs
    for curr != nil && next != nil {
        // Reverse pair
        prev.Next = next
        curr.Next = next.Next
        next.Next = curr

        // Update pointers for the next iteration
        prev = curr
        curr = curr.Next
        if curr != nil { // Ensure 'next' isn't out of bounds
            next = curr.Next
        }
    }

    return dummy.Next // Return the new head (from the dummy node)
}

// Example usage
func main() {
    // Create a simple linked list
    head := &Node{Val: 1, Next: &Node{Val: 2, Next: &Node{Val: 3, Next: &Node{Val: 4}}}}

    // Swap pairs
    newHead := swapPairs(head)

    // Print the modified list
    for newHead != nil {
        fmt.Print(newHead.Val, " ")
        newHead = newHead.Next
    }
    fmt.Println()
}