Best way to create a HASH TABLE out of an ARRAY in Swift, please?

Marie.B.B · 2023-03-01T19:14:02.647Z

Hey Team,

I wrote some working Swift code! (Yay!)

My investigation into building and using a HASH TABLE in Swift brought me here :

Medium – 23 Jan 18

Building A Hash Data Structure In Swift

Adventures In Data Structures

Reading time: 9 min read

But that looks like a heckin’ of a lot of work and was written six years ago.

The approach I took was to use the fact that Dictionary conforms to Hashable and therefore can function as a Hash Table. (Am I right about this?)

So, please find my proposed solution below for your critical review.

It works, but is this the BEST or MOST APPROPRIATE way to do this?

(Java and Python3 solutions are presented for reference.)

Thank you for your time and attention.

// Project : Code Interview Problems and Solutions (CIPS)
//
// Problem : Two Sum
//
// Difficulty : Easy
//
// Given an array of integers nums and an integer target,
// return indices of the two numbers such that they add up to target.
//
// You may assume that each input would have exactly one solution,
// and you may not use the same element twice.
//
// You can return the answer in any order.
//
// Example 1:
//
// Input: nums = [2,7,11,15], target = 9
// Output: [0,1]
// Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
//
// Example 2:
//
// Input: nums = [3,2,4], target = 6
// Output: [1,2]
//
// Example 3:
//
// Input: nums = [3,3], target = 6
// Output: [0,1]
//
// Constraints:
//
// 2 <= nums.length <= 10^4
// -10^9 <= nums[i] <= 10^9
// -10^9 <= target <= 10^9
// Only one valid answer exists.
//
// Follow-up:
//
// Can you come up with an algorithm that is less than O(n^2) time complexity?
//
// Approach : One Pass Hash Table
//
// Algorithm
//
// Iterate through nums.
//     Put nums-values and nums-indices into hash table.
//     Check if current nums-value's complement is in hash table.
//     If found, return solution
//
// Java Code
//
// class Solution {
//     public int[] twoSum(int[] nums, int target) {
//     Map<Integer, Integer> map = new HashMap<>();
//     for (int i = 0; i < nums.length; i++) {
//         int complement = target - nums[i];
//         if (map.containsKey(complement)) {
//             return new int[] { map.get(complement), i};
//         }
//         map.put(nums[i], i);
//     }
//     // If no solution, return null
//     return null;
// }
//
// Python3 Code
//
// class Solution:
//     def twoSum(self, nums: List[int], target: int) -> List[int]:
//         hashmap = {}
//         for i in range(len(nums)):
//             complement = target - nums[i]
//             if complement in hashmap:
//                 return [i, hashmap[complement]]
//             hashmap[nums[i]] = i
//
// Swift Code
//
// Note: Dictionary conforms to Hashable and performs as a hash table.
                
class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict: Dictionary<Int, Int> = [:]
        for i in 0 ..< nums.count {
            let complement:Int = target - nums[i]
            var containTest = dict.contains { $0.value == complement }
            if containTest {
                let key = dict.filter{ $0.value == complement }.keys.first!
                return [key, i]
            }
            dict[i] = nums[i]
        }
        // If no solution, return nil
        var arr = [Int]()
        return arr
    }
}

var tester = Solution()

// Testcase 1
tester.twoSum([2,7,11,15], 9) // Returns [0, 1]

// Testcase 2
tester.twoSum([3,2,4], 6) // Returns [1, 2]

// Testcase 3
tester.twoSum([3,3], 6) // Returns [0, 1]

// End of problem and solution.

Thanks, again.

AlexanderM · 2023-03-01T19:38:40.867Z

Hey Marie, welcome to the site.

Please unbold your post. It looks like you're yelling. Plus, it's counter productive. If everything is emphasized, nothing is emphasized

that Dictionary conforms to Hashable and therefore can function as a Hash Table. (Am I right about this?)

Not quite. Dictionary is a hash-table based data structure. In Python they call it dict, in C++ it's std::unordered_map, Hash in Ruby, HashMap in Java, and so on.

Conforming to Hashable means that your type can be hashed. Among other things, this lets your values be used as elements of a Set, or keys of a Dictionary. For example, you can have [[Int: Bool]: String]. That is, if you hypothetically have dictionaries whose keys are integers and values are booleans, you can use those dictionaries as keys inside other dictionaries, or as members of sets.

The rest of your question is a bit unclear to me. The TwoSum problem and solution you propose is merely using a Dictionary, but the article you posted is about how Dictionary works under the hood, and how one might go about building it for themselves.

Could you please clarify your question?

Marie.B.B · 2023-03-01T20:26:13.745Z

Thank you for the reply, @AlexanderM

The bold was copied over from TextEdit accidentally. I unbolded everything.

I will retry my question:

How would you write this line of Java code in Swift:

Map<Integer, Integer> map = new HashMap<>();

or

How would you write this line of Python3 code in Swift :

hashmap = {}

Thank you.

Nyx · 2023-03-01T20:50:38.858Z

Hi Marie

If you're asking how would a swift version of the python/java code for the two sum solver look like, here's an example:

func findTwoSumTarget(_ target: Int, in array: [Int]) -> (Int, Int)? {
    var lookup: [Int: Int] = [:]
    
    for (index, value) in array.enumerated() {
        guard value < target else {
            continue
        }
        
        if let complementIndex = lookup[value] {
            return (index, complementIndex)
        }
        
        let complement = target - value
        lookup[complement] = index
    }
    
    return nil
}

This code runs about twice as fast as your original implementation (which is not bad by the way)

Few things to note:

There's no need to return an array, you can return a tuple with the 2 indices
you can use .enumerated() to return an iterator for the for loop for (index, value) in array.enumerated() so that you don't have to access the array by index at any time
you can continue the loop if the current value is greater than the target because there's no way that value will form part of the sum
you can check if a dictionary contains a value simply by checking if that dictionary[key] is not null. That's what if let complementIndex = lookup[value] does with the added benefit that you don't have to filter afterwards and get the keys

.contains and .filter are there for more complex expressions. Checking if a dictionary has a value for a specific key is a lot simpler :)

Hope this helped

AlexanderM · 2023-03-01T21:05:21.789Z

Marie.B.B:

How would you write this line of Java code in Swift:
Map<Integer, Integer> map = new HashMap<>();

I'll break this down in a bit more detail.

Map in Java is an interface (their equivalent of a Swift protocol). HashMap is one class that implements the Map interface, but there are also others. The Swift counterpart to HashMap is Dictionary, but there's no counterpart to Map. So the equivalent Swift code would be more like this Java:

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

In Swift, that would look like:

let map: Dictionary<Int, Int> = Dictionary<Int, Int>()

Idomatic Swift code would typically use type inference to shorten it down to:

let map = [Int: Int]()

Where:

Type inference removes the need for the type annotation (: Dictionary<Int, Int>)
[Int: Int]() uses syntactic sugar. [K: V] is equivalent to Dictionary<K, V>

bbrk24 · 2023-03-01T22:25:59.741Z

AlexanderM:

Idomatic Swift code would typically use type inference to shorten it down to:
let map = [Int: Int]()

This isn't the only form that's common; I've also seen

let map2: [Int: Int] = [:] // Equivalent to {} in Python
let map3: [Int: Int] = .init()

That last one is definitely more obscure but I have seen it, for example, as a default argument to an initializer.

As a sidenote, using let here prevents you from modifying it in any way (more strict than Java final; similar to C++ const), so you probably want var instead.

Marie.B.B · 2023-03-02T00:12:11.025Z

First of all, thank you, @Nyx for some HUGE clues.

A few things . . .

I believe the "value < target" test should be "value <= target" because it is possible to have COMPLEMENT = 0 for example an "8 + 0 = 8" solution.
The return value has to be an array and can't be a tuple per problem specifications. The fixed header was provided as follows:

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {

I moved things around so they would match the "build complement" first before the "test" portion of the program.
I thought that I could lookup a Dictionary table row by VALUE, when in fact it can only be done by KEY.

As shown in this page:

iOS Dev Diary – 6 Dec 15

How to access values in a Swift Dictionary

Swift has its own dictionaries, much like Objective-C has the NSDictionary class. Although the two are bridged, they are not the same: trusty old NSDictionary methods do not work with Swift Diction…

And this page:

tutorialspoint.com

Swift - Dictionaries

Swift Dictionaries - Swift 4 dictionaries are used to store unordered lists of values of the same type. Swift 4 puts strict checking which does not allow you to enter a wrong type in a dictionary even by mistake.

I was unable to find any way to do something like var someVar = someDict[value] instead of var someVar = someDict[key] using the square bracket syntax.

If anyone knows how to do this, or if this is possible to lookup a dictionary row by value using the square brackets, please advise.

So, to make the whole thing work, the hash table build had to be dictionary[value] = index instead of dictionary[index] = value which feels logically backwards to me, but it works in this case because both sets, index and value, have unique values with no duplicates, so it doesn't matter to the computer.

(Apologies for all the debug print statements, I was stuck on this issue for quite a while.)

I'm not sure if

      let complement = target - value
      lookup[complement] = index

Was the proper way to build the hash table. I believe the hash table was supposed to be built as an identical copy of the input array nums.

Thank you, again, for all your fine clues and wisdom.

Here is Version 2 :

// Version 2

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dictionary: [Int: Int] = [:]
        for (index, value) in nums.enumerated(){
//            print("for index: \(index) value: \(value)")
            guard value <= target else {
                continue
            }
            var complement = target - value
//            print("var target: \(target) - value: \(value) = complement: \(complement)")
//            print("PREIFLET dictionary: \(dictionary)")
//            print("PREIFLET dictionary[complement]: \(dictionary[complement] ?? 666)")
            if let complementIndex = dictionary[complement] {
//                print("RETURN")
                return [complementIndex, index]
            }
            
            dictionary[value] = index
//            print("POSTASSIGN dictionary: \(dictionary)")
        }
        return [Int]()
    }
}

var tester = Solution()

// Testcase 1
tester.twoSum([2,7,11,15], 9) // Returns [0, 1]

// Testcase 2
tester.twoSum([3,2,4], 6) // Returns [1, 2]

// Testcase 3
tester.twoSum([3,3], 6) // Returns [0, 1]

// Testcase 4
tester.twoSum([9,8,7,6,0,2,4], 4) // Returns [4, 6]

// Testcase 5
tester.twoSum([0,1,2,3,4], 100) // Returns []

// End of problem and solution.