5
\$\begingroup\$

Given a 2d array, the problem is to find the largest sum, where each subsequent is >= the previous digit but < all of the 'neighbour' digits. You can only move up, down, left and right.

My solution will run in \$O(N*M)\$ time with \$O(N*M)\$ space (please correct me if I'm wrong).

The solution is as follows: Start at an arbitrary point and look for the closest largest neighbor (as described above). Once found, append it to the path and mark as visited. Continue these steps until you have no where else to visit.

Code is below, with the the answer being [10, 9, 6, 4, 2]. Thank you

nums = [
  [10,8,4],
  [9,6,8],
  [2,4,3]
]

def get_largest_neighbour(i, j, previous, visited):
    max_location = -1, -1
    max_neighbour = -1

    # look up
    if i-1 >= 0 and nums[i-1][j] < previous and visited[i-1][j] == False:
        max_neighbour = nums[i-1][j]
        max_location = i-1, j

    # look down
    if i+1 < 3:
        if nums[i+1][j] > max_neighbour and nums[i+1][j] < previous and visited[i+1][j] == False:
            max_neighbour = nums[i+1][j]
            max_location = i+1, j 

    # look left
    if j-1 >= 0:
        if nums[i][j-1] > max_neighbour and nums[i][j-1] < previous and visited[i][j-1] == False:
            max_neighbour = nums[i][j-1]
            max_location = i, j-1

    # look right
    if j+1 < 3:
        if nums[i][j+1] > max_neighbour and nums[i][j+1] < previous and visited[i][j+1] == False:
            max_neighbour = nums[i][j+1]
            max_location = i, j+1

    return max_location

def max_sum(i, j, path, visited):
    if i >= 3 or i < 0 or j >= 3 or j < 0:
        return

    if visited[i][j] == True:
        return

    # mark as visited and append to path
    visited[i][j] = True
    path.append(nums[i][j])

    # find the next largest path to search
    next_step_i, next_step_j = get_largest_neighbour(i, j, path[-1], visited)

    # there is no where to go, so stop iterating and backtrack
    if next_step_i == -1:
        return

    max_sum(next_step_i, next_step_j, path, visited)

    return path

def largest_continious_sum():
    if len(nums) <= 1:
        return 0

    visited = [[False for x in range(3)] for j in range(3)]
    path = []

    print max_sum(0, 0, path, visited)

largest_continious_sum()
\$\endgroup\$
  • 2
    \$\begingroup\$ Hi @stephens, I've rolledback your edit. So as to not invalidate answers, the code in the question must remain in its' original form. Please see What you can do once you've received answers. If you want to have your revised code reviewed, please post a follow-up question following the instructions in that post. \$\endgroup\$ – Kaz Feb 15 '16 at 11:35
  • 1
    \$\begingroup\$ No problem at all, apologies I should have read the rules more closely. \$\endgroup\$ – stephens Feb 15 '16 at 12:06
4
\$\begingroup\$

get_largest_neighbour is a big confusing function. Let's try strip it down to avoid rewriting code.

First I would create a loop to run on each of the four directions. To loop, you want to make a list of the four positions and loop over each. To do that, you can just build a simple tuple of co-ordinates were you add and subtract one from i and j in turn:

coordinates = ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))
for x, y in coordinates:

Now you need to fold all your tests to make sure they're in the right range into one, which is simple enough and more readable in my opinion:

    if not 0 <= x < len(nums) or not 0 <= y < len(nums[0]):
        continue

To break it down a bit, the range we want is for x and y to be 0 or greater, and less than the length of the lists. Rather than hardcode 3, it's better to use len of the matrix. If you're concerned about performance for larger matrices, you could precalculate these values. If either of these values isn't valid for their range, then continue is called, with will skip onto the next co-ordinate and not run the rest of the loop.

Now all you need is your actual test and re-setting the max values. For convenience, I'd grab the value of nums[x][y] before the test:

    num = nums[x][y]
    if previous > num > max_neighbour and not visited[x][y]:
        max_neighbour = num
        max_location = x, y

You notice I also changed your if test, to make a single range test and to replace == False with not. Both make it easier to see what you're actually testing.

Now your code is much simpler, easier to adjust and easier to read:

def get_largest_neighbour(i, j, previous, visited):
    max_location = -1, -1
    max_neighbour = -1
    coordinates = ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))

    for x, y in coordinates:
        if not 0 <= x < len(nums) or not 0 <= y < len(nums[0]):
            continue

        num = nums[x][y]
        if previous > num > max_neighbour and not visited[x][y]:
            max_neighbour = num
            max_location = x, y

    return max_location
\$\endgroup\$
  • \$\begingroup\$ Great ideas, thank you for taking a look. I took you function advice and implemented the following. It is much, much nicer than what I originally wrote. I have edited my original. \$\endgroup\$ – stephens Feb 15 '16 at 11:27
  • 1
    \$\begingroup\$ @stephens Glad to help! As Zak explained updating the original post isn't how Code Review works, but give it time. You might get new reviews, and then when you have a full new version you could post another question and I/others can review that version. \$\endgroup\$ – SuperBiasedMan Feb 15 '16 at 12:04
  • 1
    \$\begingroup\$ Thanks for the advice @SuperBiasedMan I'll be sure to do that in the future. \$\endgroup\$ – stephens Feb 15 '16 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.