2640. Find the Score of All Prefixes of an Array

Time: O(n)

Space: O(n)

Intuition

Maximum score after applying queries. Sort queries, sort array. For each query limit: sum of elements <= limit (prefix sum on sorted array).

Algorithm

1Sort nums. Sort queries by value. Two pointer/binary search to accumulate sum. Divide by query value.

Common Pitfalls

•Answer each query with sum of elements in nums that are <= query[i]. Sort both, use running sum.

2640.cs

// Approach: Track running max; score[i] = nums[i] + max(nums[0..i]); accumulate as prefix sums.
// Time: O(n) Space: O(n)

public class Solution
{
    public long[] FindPrefixScore(int[] nums)
    {
        int n = nums.Length;
        long[] ans = new long[n];
        int max = 0;
        long prefix = 0;

        for (int i = 0; i < n; i++)
        {
            max = Math.Max(max, nums[i]);
            prefix += nums[i] + max;
            ans[i] = prefix;
        }

        return ans;
    }
}

Was this solution helpful?