Ruby O(n) time and space - iterating smartly makes all the difference!


  • 0
    C

    Code is posted underneath.
    In both cases, the hash contains key value pairs of (target - n, i), so when we iterate through the array again, we can check the hash for a hit and if we get a hit the value is the index of the other element which adds up to target when added to the current element.

    In the method with_hash, we compute the complete hash first and then run through the array checking if we find a match.

    In the method with_hash_smarter, we do a single iteration where we populate hash with entries corresponding to whatever we've seen so far and keep checking current element in it.

    # @param {Integer[]} nums
    # @param {Integer} target
    # @return {Integer[]}
    def two_sum(nums, target)
        # brute force is O(n^2)
        # if we sort, we can do this in O(nlgn), but that's not gonna work because we need to return original indices
        # we could do it in O(n) time with O(n) space
    
        # with_hash(nums, target)
        # with_sort(nums,target)
        with_hash_smarter(nums, target)
    end
    
    # O(n) space and time - 97%ile
    def with_hash_smarter(nums, target)
        wanted = {} # set of numbers that we are looking out for 
        nums.each_with_index do |n, i|
            j = wanted[n]
            if !j.nil? 
                return [i,j].sort
            end
            wanted[target-n] = i
        end
        nil
    end
    
    
    # O(n) space and time - 19%ile
    def with_hash(nums, target)
        wanted = {}
        nums.each_with_index do |a, i|
            wanted[target-a] = i
        end
        nums.each_with_index do |b, j|
            i = wanted[b]
            # print "b: ", b,", i: ", i,", j: ", j, "\n"
            if !i.nil? && i != j
                if i > j
                    return [j, i]
                else
                    return [i, j]
                end
            end
        end
    end
    

Log in to reply
 

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