Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

 

Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

 

Constraints:

• 0 <= key, value <= 106
• At most 104 calls will be made to put, get, and remove.

class Pair<U,V>{
    public U first;
    public V second;
    public Pair(U first, V second){
        this.first = first;
        this.second = second;
    }
}

class Bucket{
    private List<Pair<Integer,Integer>> bucket;
    public Bucket(){
        this.bucket = new LinkedList<Pair<Integer,Integer>>();
    }
    
    public Integer get(Integer key){
        for(Pair<Integer,Integer> pair:this.bucket){
            if(pair.first.equals(key)){
                return pair.second;
            }
        }
        return -1;
    }
    
    public void update(Integer key,Integer value){
        boolean isFound = false;
        for(Pair<Integer,Integer> pair:this.bucket){
            if(pair.first.equals(key)){
                isFound = true;
                pair.second = value;
            }
        }
        if(!isFound){
            this.bucket.add(new Pair<Integer,Integer>(key,value));
        }
    }
    
    public void remove(Integer key){
        for(Pair<Integer,Integer> pair : this.bucket){
            if(pair.first.equals(key)){
                this.bucket.remove(pair);
                break;
            }
        }
    }
}



class MyHashMap {
    private int key_space;
    private List<Bucket> hash_table;

    public MyHashMap() {
        this.key_space = 2069;
        this.hash_table = new ArrayList<Bucket>();
        for(int i =0;i<key_space;i++){
            this.hash_table.add(new Bucket());
        }
    }
    
    public void put(int key, int value) {
        int hash_key = key % this.key_space;
        this.hash_table.get(hash_key).update(key,value);
    }
    
    public int get(int key) {
        int hash_key = key % this.key_space;
        return this.hash_table.get(hash_key).get(key);
    }
    
    public void remove(int key) {
        int hash_key = key % this.key_space;
        this.hash_table.get(hash_key).remove(key);
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

Complexity Analysis
Time Complexity: for each of the methods, the time complexity is $\mathcal{O}(\frac{N}{K})$ where $N$ is the number of all possible keys and $K$ is the number of predefined buckets in the hashmap, which is 2069 in our case.
In the ideal case, the keys are evenly distributed in all buckets. As a result, on average, we could consider the size of the bucket is $\frac{N}{K}$.
Since in the worst case we need to iterate through a bucket to find the desire value, the time complexity of each method is $\mathcal{O}(\frac{N}{K})$.
Space Complexity: $\mathcal{O}(K+M)$ where $K$ is the number of predefined buckets in the hashmap and $M$ is the number of unique keys that have been inserted into the hashmap.

Find Winner on a Tic Tac Toe Game

 Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

• Players take turns placing characters into empty squares ' '.
• The first player A always places 'X' characters, while the second player B always places 'O' characters.
• 'X' and 'O' characters are always placed into empty squares, never on filled ones.
• The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. return the winner of the game if it exists (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.

 

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: A wins, they always play first.

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: B wins.

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.

 

Constraints:

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= rowi, coli <= 2
• There are no repeated elements on moves.
• moves follow the rules of tic tac toe.

class Solution {
    public String tictactoe(int[][] moves) {
       int n = 3;
       int[] rows = new int[n];
       int[] cols = new int[n];
       int player = 1;
       int diag = 0;
        int antidiag = 0;
        
        for(int[] move:moves){
            int row = move[0];
            int col = move[1];
            
            rows[row] += player;
            cols[col] += player;
            
            if(row == col){
                diag+= player;
            }
            
            if(row + col == n-1){
                antidiag += player;
            }
            
            if(Math.abs(diag) == n || Math.abs(antidiag) == n || Math.abs(rows[row]) == n || Math.abs(cols[col]) == n){
                return player == 1 ? "A":"B";
            }
            player *= -1;
        }
        return moves.length == n * n ? "Draw" : "Pending";
    }
}

Time complexity: $O(m)$
For every move, we update the value for a row, column, diagonal, and anti-diagonal. Each update takes constant time. We also check if any of these lines satisfies the winning condition which also takes constant time.
Space complexity: $O(n)$
We use two arrays of size n to record the value for each row and column, and two integers of constant space to record to value for diagonal and anti-diagonal.

Find N Unique Integers Sum up to Zero

 Find N Unique Integers Sum up to Zero

Given an integer n, return any array containing n unique integers such that they add up to 0.

 

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Example 2:

Input: n = 3
Output: [-1,0,1]

Example 3:

Input: n = 1
Output: [0]

 

Constraints:

• 1 <= n <= 1000

class Solution {
    public int[] sumZero(int n) {
        if(n == 0){
            return new int[] {0};
        }
        int value = n;
        int [] uniqueIntegers = new int[n];
        for(int i=0,j=n-1;i<j;i++,j--){
            uniqueIntegers[i]= value;
            uniqueIntegers[j] = value * -1;
            value--;
        }
       return uniqueIntegers;
    }
}

TC : O(N) SC: O(N)

Sign of the Product of an Array

 Sign of the Product of an Array

There is a function signFunc(x) that returns:

• 1 if x is positive.
• -1 if x is negative.
• 0 if x is equal to 0.

You are given an integer array nums. Let product be the product of all values in the array nums.

Return signFunc(product).

 

Example 1:

Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1

Example 2:

Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0

Example 3:

Input: nums = [-1,1,-1,1,-1]
Output: -1
Explanation: The product of all values in the array is -1, and signFunc(-1) = -1

 

Constraints:

• 1 <= nums.length <= 1000
• -100 <= nums[i] <= 100

Solution 1:

class Solution {
    public int arraySign(int[] nums) {
        int sign = 1;
        for(int num:nums){
            if(num == 0){
                return 0;
            }
            if(num < 0){
                sign *= -1;
            }
        }
        return sign;
    }
}

Solution 2:

class Solution {
    public int arraySign(int[] nums) {
        int countNeg = 0;
        for(int num:nums){
            if(num == 0){
                return 0;
            }
            if(num < 0){
                countNeg++;
            }
        }
        return countNeg % 2 == 0 ? 1 : -1;
    }
}

TC: O(n) SC: O(1)

Network Delay Time - Python Solution

 There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2




Output: 2

class Solution(object):
    def networkDelayTime(self, times, N, K):
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        dist = {node: float('inf') for node in range(1, N+1)}
        seen = [False] * (N+1)
        dist[K] = 0

        while True:
            cand_node = -1
            cand_dist = float('inf')
            for i in range(1, N+1):
                if not seen[i] and dist[i] < cand_dist:
                    cand_dist = dist[i]
                    cand_node = i

            if cand_node < 0: break
            seen[cand_node] = True
            for nei, d in graph[cand_node]:
                dist[nei] = min(dist[nei], dist[cand_node] + d)

        ans = max(dist.values())
        return ans if ans < float('inf') else -1

 

String Transforms Into Another String - Python Solution

 Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

 

Example 1:

Input: str1 = "aabcc", str2 = "ccdee"
Output: true
Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.

Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        hashmap = {}
        hashset = set()
        
        for i in range(len(str1)):
            hashset.add(str2[i])
            if str1[i] in hashmap and hashmap[str1[i]] != str2[i]:
                return False
            hashmap[str1[i]] = str2[i]
        
        if str1 != str2 and len(hashset) == 26 and len(hashmap) == 26:
            return False
        return True
        
        

O(n) and O(n)