Teaching Kids Programming – Finding Largest K Value with its Negative in Array using Hash Table/Set (K and -K)


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, return the largest integer k where k and -k both exist in nums (they can be the same integer). If there’s no such integer, return -1.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [-4, 1, 8, -5, 4, -8]
Output
8

Example 2
Input
nums = [5, 6, 1, -2]
Output
-1

Example 3
Input
nums = [1, 2, 0, 3, 4]
Output
0

Hint:
Consider using a set to quickly check if the additive inverse of a number is present or not already.

Algorithms to Find the Largest K and -K using Hash Table/Set

We can bruteforce: try each number and check if its negative number is also in the array:

1
2
3
4
5
6
7
class Solution:
    def solve(self, nums):
        ans = -math.inf
        for i in nums:
            if -i in nums:
                ans = max(ans, -i)
        return ans if ans != -math.inf else -1             
class Solution:
    def solve(self, nums):
        ans = -math.inf
        for i in nums:
            if -i in nums:
                ans = max(ans, -i)
        return ans if ans != -math.inf else -1             

The problem is that checking a number in array takes O(N) time – and if we go through each number, that is going to make it O(N^2) quadratic – which is inefficient (however, it is O(1) space). We can use a hash table (dictionary, Counter) or hash set to quickly check if the additive inverse (negative) is also present in the array.

1
2
3
4
5
6
7
8
class Solution:
    def solve(self, nums):
        ans = -math.inf
        seen = set(nums)
        for i in seen:
            if -i in seen:
                ans = max(ans, -i)
        return ans if ans != -math.inf else -1
class Solution:
    def solve(self, nums):
        ans = -math.inf
        seen = set(nums)
        for i in seen:
            if -i in seen:
                ans = max(ans, -i)
        return ans if ans != -math.inf else -1

if K and -K are not found in the array, we need to be able to return -1. So -math.inf is the smallest number. If it hasn’t been change we know there is no K and -K. If we put zero, we can’t distinguish between [0] and [1].

The time complexity is O(N) linear and space complexity is also O(N) as we are using additional linear space e.g. hash table to store the numbers that we have seen.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
a WordPress rating system
512 words
Last Post: Teaching Kids Programming - Find First Recurring Character using Hash Table/Set
Next Post: Teaching Kids Programming - Find Subsequence of Length K With the Largest Sum (Greedy, Sliding Window)

The Permanent URL is: Teaching Kids Programming – Finding Largest K Value with its Negative in Array using Hash Table/Set (K and -K)

Leave a Reply