prefix sum

Question 1

find the highest altitude:
code

Answer 1

def largestAltitude(gain: List[int]) -> int:
    max_alt, curr = 0, 0
    for g in gain:
        curr += g
        max_alt = max(max_alt, curr)
    return max_alt

Question 2

find the highest altitude: intuition

Answer 2

Initialize the variable currentAltitude to 0; this is the current altitude of the biker.

Initialize the variable highestPoint to currentAltitude, as the highest altitude we have seen is 0.

Iterate over the gain in altitude in the list gain and add the current gain altitude
Gain to the variable currentAltitude.
Update the variable highestPoint as necessary.

Return highestPoint.

Question 3

find pivot index:
intuition

Answer 3

Initialize variables rightsum to the total sum of the nums array and leftsum to be zero.

Iterate over the list using enumerate, which gives the index and the element of each item in the array.

First, update the right sum by subtracting ele. This adjusts the sum of elements to the right of the current index.

Compare left sum to right sum, if they are equal, return idx.

If not equal, continue on by updating the left sum.

If the loop exits without returning a pivot, return -1

Question 4

find pivot index:
code

Answer 4

def pivotIndex(nums):
    leftSum, rightSum = 0, sum(nums)
    for idx, ele in enumerate(nums):
        rightSum -= ele
        if leftSum == rightSum:
            return idx      # Return the pivot index...
        leftSum += ele
    return -1

Question 5

make sum divisible by p: intuition

Answer 5

Initialize n as the size of nums and totalSum to 0.

Calculate the total sum and target remainder:

Iterate over each element in nums to compute totalSum as the sum of all elements modulo p.

Set target as totalSum % p.
If target is 0, return 0 (the array is already divisible by p).
Use a hash map to track prefix sums modulo p:

Initialize modMap with 0 mapped to -1 to handle cases where the entire prefix is the answer.
Initialize currentSum to 0 and minLen to n.
Iterate over the array:

Update currentSum with the current element, taking modulo p.

Calculate needed as the difference between currentSum and target, adjusted to be positive by adding p and taking modulo p.

Check if needed exists in modMap:
If it does, calculate the length of the subarray and update minLen if it’s smaller.
Store the current remainder and its index in modMap.
Return the result:

If minLen is still n, return -1 (no valid subarray found).
Otherwise, return minLen.

Question 6

make sum divisible by p: code

Answer 6

def minSubarray(nums: List[int], p: int) -> int:
    n = len(nums)
    total_sum = 0

    for num in nums:
        total_sum = total_sum + num % p

    target = total_sum % p
    if target == 0:
        return 0

    mod_map = {
        0: -1
    }

    current_sum = 0
    min_len = n

    for i in range(n):
        current_sum = (current_sum + nums[i]) % p

        needed = (current_sum - target + p) % p
        if needed in mod_map:
            min_len = min(min_len, i - mod_map[needed])

        mod_map[current_sum] = i

    return -1 if min_len == n else min_len