Leetcode 747: Largest Number At Least Twice of Others

Problem Definition

Given an array of integers, find the index of the largest element in the array which is at least twice as much as every other number in the array. If no such element exists, return -1. -- Leetcode 747

Input nums: [Int]

Output idx: Int

Solution

    def dominantIndex(nums):
        if len(nums) < 2:
          return 0

        d = {}
        for i, n in enumerate(nums):
          d[n] = i

        nums.sort()

        if (nums[-1] >= nums[-2] * 2):
          return d[nums[-1]]

        return -1

Explanation and reasoning

Whenever possible I like to reduce my algorithm designs to another problem. For this problem I reduced it to sorting by introducing an additional intermediary dictionary, which is populated by {value : index} pairs upon a single forward scan of the input. Once this structure is populated, we simply sort the input and compare the last and second to last elements. Because the list is now in sorted order, if the predicate holds true for the second to last element, it holds true for every other element preceding it. If the test is true, we index into the dictionary using the value, and return the associated index.