What is a more optimal algorithm for this problem?

by

Suppose you have an array A of N integers. In one round, you make changes as follows (based on the array snapshot at the beginning of the round):

  • -= 1 if greater than both adjacent (on both sides)
  • += 1 if less than both adjacent (on both sides)

The one on the edges/ends never change, and you keep going while a change was made the previous round.

A simple algorithm looks like:

    while True:
        prior = A
        cur = A[:]
        for i in range(1, len(cur) - 1):
            if prior[i - 1] > prior[i] and prior[i + 1] > prior[i]:
                cur[i] += 1
            elif prior[i - 1] < prior[i] and prior[i + 1] < prior[i]:
                cur[i] -= 1
        if cur == prior:
            break
        A = cur
    return A

This was for a coding assessment I recently took. Here’s a couple examples:

Input: [1, 6, 3, 4, 3, 5]
Returns: [1, 4, 4, 4, 4, 5]

Input: [100, 50, 40, 30]
Returns: [100, 50, 40, 30]

Explanation for 1st case:

1 and 5 at the ends never change since they don’t have both neighbours. This will also be true for any testcase. Next state would be as below,

[ 1, 5, 4, 3, 4, 5]

  • arr[2] = 5 since 1 < 6 > 3, 6 gets reduced by 1 making it 5

  • arr[3] = 4 since 6 > 3 < 4, 3 gets increased by 1 making it 4.

  • arr[4] = 3 since 3 < 4 > 3, 4 gets reduced by 1 making it 3.

  • arr[5] = 4 since 4 > 3 < 5, 3, gets increased by 1 making it 4.

    [ 1, 5, 4, 3, 4, 5] becomes [1, 4, 4, 4, 4, 5] in a similar fashion as above and stops here since no further operations can be performed.

Explanation for 2nd case:

No action is taken on the array since none of the non-border elements have neighbours where both are either smaller or greater.

  • should be the output for first example would be [1, 5, 4, 4, 4, 5]

    – 

  • @sahasrara62 Of course no. In the next round 1, 5, 4 changes to 1, 4, 4,

    – 

  • If you have working code that you want to optimize, consider posting in Code Review instead.

    – 

  • What is the maximum length of the array possible?

    – 

  • there’s no such thing as “most optimal” because by definition optimal is the best of all possible solutions. You cannot have a “least optimal” solution because it wouldn’t be optimal, as a consequence there cannot be a most optimal solution.

    – 




The test if cur == prior is inefficient – especially if the list is long.

You can avoid multiple indexed look-ups by acquiring the “mid” value just once

Better to use a simple boolean as follows:

def process(A):
    while True:
        prior = A
        cur = A.copy()
        flag = False
        for i in range(1, len(cur) - 1):
            if (v := prior[i]) > prior[i-1] and v > prior[i+1]:
                cur[i] -= 1
                flag = True
            elif v < prior[i-1] and v < prior[i+1]:
                cur[i] += 1
                flag = True
        if not flag:
            break
        A = cur
    return A

Leave a Comment