Different idea, incomplete... help?

  • 0

    Before I came up with my merge sort solution, I tried another idea: Attach the index to each number, then sort the numbers (with their indexes), then see how much each number moved. Take for example input [5, 2, 6, 1, 3] and sort it so it's [1, 2, 3, 5, 6].

    The 5 moved three steps to the right, and that's because there were three smaller numbers on its right initially. So in the result, write down "3" for the 5. Well, it doesn't quite work, but that's the basic idea.

    You can see that it doesn't quite work by checking the 2: It moves zero steps, even though there was a smaller number on its right, namely the 1. But while the 1 did push the 2 one step to the right, the 5 pushed it one step to the left, so that overall the 2 didn't move.

    So maybe the index differences of the basic idea can somehow be adjusted by the number of rightmovers? Here are the numbers of rightmovers for each index:

    index:  [0, 1, 2, 3, 4]
    before: [5, 2, 6, 1, 3]
    after:  [1, 2, 3, 5, 6]
    rightmover changes: [1, 0, 1, -1, -1]
    1 numbers moved right from index 0
    1 numbers moved right from index 1
    2 numbers moved right from index 2
    1 numbers moved right from index 3
    0 numbers moved right from index 4

    That was computed by this code in O(nlogn) for sorting plus O(n) for the rest:

    nums = [5, 2, 6, 1, 3]
    rightmover_changes = [0] * len(nums)
    indexed_and_sorted = sorted(enumerate(nums), key=lambda x: x[::-1])
    for i, (orig_i, num) in enumerate(indexed_and_sorted):
        if orig_i < i:
            rightmover_changes[orig_i] += 1
            rightmover_changes[i] -= 1
    print 'index: ', range(len(nums))
    print 'before:', nums
    print 'after: ', sorted(nums)
    print 'rightmover changes:', rightmover_changes
    rightmovers = 0
    for i, change in enumerate(rightmover_changes):
        rightmovers += change
        print '{} numbers moved right from index {}'.format(rightmovers, i)

    I might try again to make this work, but maybe I won't. For now I just wanted to put this out here.

  • 0

    what if you track not the right movers, but the leftmovers?

    so for 1 you have that it moved 3 positions left, hence it's "area of influence" in the sorted array would be from 1 to 3.

    at each point of the array you track how many leftmovers "influence" the current number:

    for 2, you calculate 1-1 (index difference, move) +1 (number of symbols that were initially after 2)
    and for 3, that would be 2-4 (move) + 1 (for the 1 that moved to the left) => total s to -1, so
    I didn't think through how to track the number of "influencers" - with stack maybe ?

    would this work?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.