Showing posts with label hash table. Show all posts
Showing posts with label hash table. Show all posts

Saturday, August 29, 2015

Single Number

Problem Description
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Solutions
I. Using Hash Table
We can solve this problem by simply counting the number of times a number appeared.
Java Code
public class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i = 0; i<nums.length; i++){
            
            if(!map.containsKey(nums[i])){
                map.put(nums[i], false);
            }else{
                map.put(nums[i], true);
            }
        }
        for(int i: map.keySet()){
            if (!map.get(i)) return i;
        }
        return 0;
    }
}
II. Bit manipulation
In this solution, we have the following observation, given an integer N:
0 ^ N = N
N ^ N = 0
Where ^ is the XOR operator.
public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i<nums.length; i++){
            
            result ^= nums[i];
        }
        return result;
    }
}

Wednesday, August 19, 2015

Maximum Rectangle

Problem Description
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Solutions
I. Solution by finding largest rectangle in histogram
class Solution:
    # @param matrix, a list of lists of 1 length string
    # @return an integer
    def maximalRectangle(self, matrix):
        if not matrix:
            return 0
        h, w = len(matrix), len(matrix[0])
        m = [[0]*w for _ in range(h)]
        for j in range(h):
            for i in range(w):
                if matrix[j][i] == '1':
                    m[j][i] = m[j-1][i] + 1
        return max(self.largestRectangleArea(row) for row in m)
    
    def largestRectangleArea(self, height):
        '''
        This uses the way we calculate maximum rectangle in histogram
        '''
        height.append(0)
        stack, area = [], 0
        for i in range(len(height)):
            while stack and height[stack[-1]] > height[i]:
                h = height[stack.pop()]
                w = i if not stack else i-stack[-1]-1
                area = max(area, h*w)
            stack.append(i)
        return area