Optimizing Array Sums via Negation

The first challenge involves modifying an integer array to achieve the highest possible sum after performing a specific number of negation operations. Given an array values and an integer flipCount, the goal is to negate elements exactly flipCount times.

Strategy Analysis

The optimal approach relies on prioritizing negative numbers. Converting a negative number to a positive increases the total sum. Therefore, the greedy strategy involves:

• Sorting the array to access the smallest values (most negative) first.
• Iterating through the array and flipping negative numbers until either the array ends or the operation count is exhausted.
• If operations remain after all negatives are positive, check the parity of the remaining count. If odd, the smallest absolute value in the modified array must be negated once to minimize the loss.

Implementation

The following solution sorts the input initially to handle negatives. If operations remain, it ensures the smallest magnitude element is adjusted based on the remaining count parity.

class Solution {
    public int maximizeArraySum(int[] data, int flipCount) {
        Arrays.sort(data);
        int index = 0;
        
        // Prioritize flipping negative numbers
        while (index < data.length && flipCount > 0 && data[index] < 0) {
            data[index] = -data[index];
            flipCount--;
            index++;
        }
        
        // If flips remain, check parity
        if (flipCount % 2 == 1) {
            Arrays.sort(data);
            data[0] = -data[0];
        }
        
        int total = 0;
        for (int val : data) {
            total += val;
        }
        return total;
    }
}

Circuit Completion via Fuel Management

The second problem presents a circular route with multiple stations. Each station provides a specific amount of fuel supply, and traveling to the next station consumes a specific amount demand. The objective is to identify the starting station index that allows completing the full circuit, or return -1 if impossible.

Strategy Analysis

This problem can be modeled using net fuel gain. For each station, calculate net = supply[i] - demand[i]. Two conditions determine the solution:

• Global Feasibility: If the total sum of net fuel across all stations is negative, completing the circuit is impossible regardless of the start point.
• Local Feasibility: If the total sum is non-negative, a solution exists. We iterate through the stations, maintaining a running tank balance. If the balance drops below zero at any point, the current starting point is invalid, and the search resets to the next station.

Implementation

The algorithm tracks the total net fuel and the current tank level simultaneously. If the tank empties, the start index shifts forward.

class Solution {
    public int findStartingStation(int[] supply, int[] demand) {
        int totalNetFuel = 0;
        int currentTank = 0;
        int startStation = 0;
        
        for (int i = 0; i < supply.length; i++) {
            int net = supply[i] - demand[i];
            totalNetFuel += net;
            currentTank += net;
            
            // If tank drops below zero, reset start point
            if (currentTank < 0) {
                startStation = i + 1;
                currentTank = 0;
            }
        }
        
        return totalNetFuel >= 0 ? startStation : -1;
    }
}

Rating-Based Candy Distribution

The final challenge involves distributing candies to children standing in a line based on their performance ratings. Each child must receive at least one candy, and any child with a higher rating than their immediate neighbor must receive more candies than that neighbor. The goal is to minimize the total number of candies distributed.

Strategy Analysis

Since a child's candy count depends on both left and right neighbors, a single pass is insufficient. The solution requires two passes to satisfy local constraints independently:

• Left-to-Right Pass: Ensure that if a child has a higher rating than the left neighbor, they receive more candies.
• Right-to-Left Pass: Ensure that if a child has a higher rating than the right neighbor, they receive more candies. This pass must respect the counts established in the first pass by taking the maximum value.

Implementation

We initialize an allocation array with 1s. The first loop handles increasing ratings from left to right. The second loop handles decreasing ratings from right to left, updating allocations only when necessary to satisfy the condition while preserving previous constraints.

class Solution {
    public int calculateMinimumCandies(int[] performanceScores) {
        int n = performanceScores.length;
        int[] allocations = new int[n];
        Arrays.fill(allocations, 1);
        
        // Left to right: handle right neighbor higher than left
        for (int i = 1; i < n; i++) {
            if (performanceScores[i] > performanceScores[i - 1]) {
                allocations[i] = allocations[i - 1] + 1;
            }
        }
        
        // Right to left: handle left neighbor higher than right
        for (int i = n - 2; i >= 0; i--) {
            if (performanceScores[i] > performanceScores[i + 1]) {
                allocations[i] = Math.max(allocations[i], allocations[i + 1] + 1);
            }
        }
        
        int totalCandies = 0;
        for (int count : allocations) {
            totalCandies += count;
        }
        return totalCandies;
    }
}