Make a copy of the array $$$s$$$: call it $$$t$$$. Sort $$$t$$$ in non-decreasing order, so that $$$t_1$$$ is the maximum strength and $$$t_2$$$ — the second maximum strength.

Then for everyone but the best person, they should compare with the best person who has strength $$$t_1$$$. So for all $$$i$$$ such that $$$s_i≠t_1$$$, we should output $$$s_i−t_1$$$. Otherwise, output $$$s_i−t_2$$$ — the second highest strength, which is the next best person.

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(map(int, input().split()))
    t = sorted(s)
    for i in range(n):
        if s[i] != t[-1]:
            s[i] = s[i] - t[-1]
        else:
            s[i] = s[i] - t[-2]
    print(*s)

We precalculate some array $$$A_{i}$$$, that $$$A_{i} = 1$$$, if $$$s_{i} = s_{i + 1}$$$, else $$$A_{i} = 0$$$. Now for any query ($$$l$$$, $r$), we need to find sum of $$$A_{i}$$$, such that $$$(l ≤ i < r)$$$. It has not become a range sum query problem. To solve this problem, we can precalculate a prefix sum array $$$Sum$$$, where $$$Sum_{i} = A_{1} + A_{2} + ... + A_{i}$$$. Then the sum of the interval ($$$l$$$, $$$r$$$) is $$$Sum_{r} — Sum_{l-1}$$$.

s = input()
m = int(input())
queries = []

for _ in range(m):
    queries.append(list(map(int, input().split())))

pref = [0]
for indx in range(len(s) - 1):
    if s[indx] == s[indx + 1]:
        pref.append(pref[-1] + 1)
    
    else:
        pref.append(pref[-1])


for left, right in queries:
    print(pref[right - 1] - pref[left - 1])

Sort the array in ascending order.

To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:

1. Sort the given input array in ascending order.
2. It iterates through the sorted array. For each value, check if the current serving time is greater than the total waiting time of the current person (the sum of the previous satisfied customer's serving time ) . If it is, it means the person is satisfied. Otherwise, the person is not satisfied and will leave the queue automatically.

Time Complexity: O(n), n is the size of the queue.

Space Complexity: O(1)

    n = int(input())
    time = sorted(map(int, input().split()))

    ans = waitTime = 0
    for i in range(n):
        if waitTime <= time[i]:
            ans += 1
            waitTime += time[i]
    
    print(ans)

If there is at least a prefix or a suffix with non-positive sum, we can delete that prefix/suffix and end up with an array with sum $$$≥$$$ the sum of the whole array. So, if that's the case, the answer is "NO".

Otherwise, all the segments that Aman can choose will have a sum $$$<$$$ than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Time complexity: O(n)

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    total_sum = 0
    for num in a:
        total_sum += num
        if total_sum <= 0:
            return False
    total_sum = 0
    for i in range(n - 1, -1, -1):
        total_sum += a[i]
        if total_sum <= 0:
            return False
    return True

T = int(input())
for _ in range(T):
    if solve():
        print("YES")
    else:
        print("NO")

Track the maximum value encountered.

Initializes the answer $$$ans$$$ as $$$YES$$$ assuming initially that it's possible to reach every position. Iterates over the given input array in the sequence (except the last one) using a loop. At each position, update the maximum value encountered so far $$$currMax$$$ among the first $$$i$$$ elements. If $$$currMax$$$ becomes greater than $$$(i + 1)$$$ (indicating there's a gap between the maximum reachable position and the current position), and the corresponding rule for that position is $$$0$$$, update the answer to $$$NO$$$ and break out of the loop.

Time Complexity: O(n), n is the size of the input array. Space Complexity: O(1)

    n = int(input())
    nums = list(map(int, input().split()))
    rules = input()

    ans = 'YES'
    currMax = 0
    for i in range(n - 1):
        currMax = max(currMax, nums[i])
        if currMax > i + 1 and rules[i] == '0':
            ans = 'NO'
            break

    print(ans)

How would you solve count subarrays with sum equal to $$$k$$$ optimally using the concept of prefix sum?

We will keep track of the prefix product.

Lets call the current prefix product $$$currentPrefix$$$.
If $$$currentPrefix$$$ is positive,

1. If we have seen another positive prefix before, it means that the segment of the currentPrefix excluding the previous prefix would give us a positive product, because $$$(+)*(+) = (+)$$$. The amount of previous positive prefixes tells us how many segments with positive product we can have at the current prefix.
2. Similarly, if we have seen a negative prefix before, it means that the remaining part of the current segment has to be negative, because $$$(-)*(-) = (+)$$$.

In the same manner, if $$$currentPrefix$$$ is negative,

1. We increment the negative product segments by the number of previous positive prefixes, because $$$(+)*(-) = (-)$$$.
2. We increment the positive product segments by the number of previous negative prefixes, because $$$(-)*(+) = (-)$$$.

n = int(input())
a = list(map(int, input().split()))

pos_prefixes = 1 # as an identity, to take into account a whole prefix
neg_prefixes = 0

pos_seg_count = 0
neg_seg_count = 0

prefix = 1

for num in a:
    prefix *= (num//abs(num)) # we only want the sign, not the magnitude

    if prefix > 0:
        pos_seg_count += pos_prefixes
        neg_seg_count += neg_prefixes
        pos_prefixes += 1
        
    else:
        pos_seg_count += neg_prefixes
        neg_seg_count += pos_prefixes
        neg_prefixes += 1

print(neg_seg_count, pos_seg_count)