No median calculation O(n) time O(1) space complexity with explanation


#1

Think it this way: Suppose you have 1 gap, 5 people on left of it and 500 on right of it. How would you fill this gap?

To shift the 5 guys from left instead of shifting the 500 guys from other side, right?

That’s the whole theory behind median approach, the lesser ones move towards the larger ones to fill the gaps (median will always be toward the higher side).

So no need to find out median. For each individual gap, calculate the no. of people in its left and its right and add the ones which are minimum.

That can be done using two pointers:

int Solution::seats(string A) {
    int l = 0, r = 0, i = 0, j = A.length()-1, ans = 0, mod = 10000003;
    // l : no. of people in left
    // r : no. of people in right
    while(i <= j) {
        while(i <= j && A[i] == 'x') {
            l++; i++;
        }
        while(i <= j && A[j] == 'x') {
            r++; j--;
        }
        if(i <= j) {
            if(l <= r) {
                ans = (ans + l) % mod;
                i++;
            } else {
                ans = (ans + r) % mod;
                j--;
            }
        }
    }
    return ans;
}

#2

Brilliant solution!! This could be included in the editorial.