🏰 Palace Window

Search

SearchSearch

Analytical

Problems that require the answerer to reason about some equation or compute some quantity in order to solve them but don’t really fit firmly in any other solution methods.

 

Sum of Odds & Evens Equal After Removal

Given an array of integers, choose one indices to remove that makes the even indexed elements sum to the same value as the odd index elements. Return the total number of indices that can be removed in this way.

Explore

  6 1 7 4 1
  csl -> 6,0 6,1 13,1 13,5 14,5
  csr -> 1,0 1,4 8,4  8,5  14,5
  1. Calculate the cumulative sum from the left & right of odd & even indices.
  2. For all i, compare csl[i-1]→even + csr[i+1]→odd to csl[i-1]→odd + csr[i+1]→even because removing one index from csr swaps even & odd sums.
  3. Return the number of comparisons that return true.

Python Solution

class Solution:
    def waysToMakeFair(self, a) -> int:
        csl, csr, soln, N = [[a[0], 0]], [], 0, len(a)
        if N == 0:
            return 0
        if N == 1:
            return 1
 
        for i in range(1, N):
            if i % 2 == 0:
                csl += [[csl[i - 1][0] + a[i], csl[i - 1][1]]]
            else:
                csl += [[csl[i - 1][0], csl[i - 1][1] + a[i]]]
 
        if (N - 1) % 2 == 0:
            csr += [[a[N - 1], 0]]
        else:
            csr += [[0, a[N - 1]]]
 
        # TODO: make CSR go the same direction as the input array to simplify
        for i in range(1, N):
            j = N - 1 - i
            if j % 2 == 0:
                csr += [[csr[i - 1][0] + a[j], csr[i - 1][1]]]
            else:
                csr += [[csr[i - 1][0], csr[i - 1][1] + a[j]]]
 
        if csr[N - 2][0] == csr[N - 2][1]:
            soln += 1
        if csl[N - 2][0] == csl[N - 2][1]:
            soln += 1
 
        for i in range(1, N - 1):
            j = N - 1 - i
            if csl[i - 1][0] + csr[j - 1][1] == csl[i - 1][1] + csr[j - 1][0]:
                soln += 1
 
        return soln

Complexity

We calculate the cumulative sums from the left & the right using O(n) space & then iterate them to find which indices can be removed in O(n) total time.

 

Left & Right Sum Differences

Given an array of integers, find the difference in the absolute value of the cumulative sum from the left & the right at each index. The value at the current index is not included in the calculations.

Python Solution

class Solution:
    def leftRigthDifference(self, a) -> List[int]:
        n = len(a)
        if n == 1:
            return [0]
 
        csl, csr, soln = [0] * n, [0] * n, [0] * n
 
        csl[0] = a[0]
        csr[n - 1] = a[n - 1]
        for i in range(1, n):
            j = n - 1 - i
            csl[i] = csl[i - 1] + a[i]
            csr[j] = csr[j + 1] + a[j]
 
        soln[0] = csr[1]
        soln[n - 1] = csl[n - 2]
        for i in range(1, n - 1):
            soln[i] = abs(csl[i - 1] - csr[i + 1])
 
        return soln

 

Break a Palindrome

Given a palindrome, make the lexicographically smallest non palindromic string using one operation. Lexicographical smallest is just the first in alphabetical order.

Explore

a b c c b a a a a a a a a b a b a b a b a a b b a b

  1. From the left up to the middle index, skipping the middle letter in odd length strings, lower any non ‘a’ to ‘a’ & return the mutated string.
  2. If all characters are ‘a’, then raise the last letter to ‘b’. This can be the fall through case.

Python Solution

def f(s: str) -> str:
    p = list(s)
    N = len(p)
    if N == 1:  # i.e. no way to break the palindrome
        return ""

    middle = N // 2

    # leaves out the middle in the odd case
    for i in range(middle):
        if p[i] != "a":
            p[i] = "a"
            return p.join("")

    p[N - 1] = "b"
    return p.join("")

Complexity

We iterate the first half of the string in O(N) time & because this is Python & strings are immutable, when we mutate one character, we make a copy of the string in O(N) time using O(N), but we only do this once. Our solution is then O(N) time & O(N) space.

Graph View