Leetcode 2. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Analysis:

• Initialize current node to dummy head of the returning list.
• Initialize carry to $0$.
• Initialize $p$ and $q$ to head of $l1$ and $l2$ respectively.
• Loop through lists $l1$ and $l2$ until you reach both ends.
  • Set $x$ to node $p$‘s value. If $p$ has reached the end of $l1$, set to $0$.
  • Set $y$ to node $q$‘s value. If $q$ has reached the end of $l2$, set to $0$.
  • Set $sum=x+y+carry$.
  • Update $carry=sum/10$.
  • Create a new node with the digit value of $(summod10)$ and set it to current node’s next, then advance current node to next.
  • Advance both $p$ and $q$.
• Check if $carry=1$, if so append a new node with digit $1$ to the returning list.
• Return dummy head’s next node.

Time complexity: O(max(m, n))

Space complexity: O(max(m, n))

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // O(n) O(1)
        
        if (l1 == null || l2 == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        int sum = 0;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int num1 = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;
            
            sum = num1 + num2 + carry;
            
            // update the next node
            cur.next = new ListNode(sum % 10);
            
            cur = cur.next;
            carry = sum / 10;
            
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        
        // Check the last corner case
        if (carry != 0) {
            cur.next = new ListNode(carry);
        }
        
        return dummy.next;
    }
}

Leetcode 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.

• The linked lists must retain their original structure after the function returns.

• You may assume there are no cycles anywhere in the entire linked structure.

• Your code should preferably run in O(n) time and use only O(1) memory.

Analysis:

3 steps:

• Get the length of both list
• Let the longer list to go before len1-len2 steps
• Make the lists go further, if they’re the same, then we find it

Time complexity: O(m + n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // O(m + n)
        
        if (headA == null || headB == null) {
            return null;
        }
        
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        // Let the longer list to go before lenA - lenB 
        for (int i = 0; i < Math.abs(lenA - lenB); i++) {             if (lenA > lenB) {
                headA = headA.next;
            } else {
                headB = headB.next;
            }
        }
        
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
    
    public int getLength(ListNode head) {
        int len = 0;
        
        while (head != null) {
            head = head.next;
            len++;
        }
        
        return len;
    }
}

Leetcode 217, 219 & 220. Contains Duplicate I II & III

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Analysis:

Simply put the values in a set. Then check the size of the set equals to the length of th array.

Time complexity: O(n)

Space complexity: O(1)

Below is the code:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        // O(n) O(1)
        
        if (nums == null || nums.length == 0) {
            return false;
        }
        
        HashSet set = new HashSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        
        if (set.size() == nums.length) {
            return false;
        }
        
        return true;
    }
}

Followup:

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Analysis:

To find the the required result. We can put the integers in a hash table. Integer is the key, index is the value. Then we check whether there’s two keys are the same and the value of these two keys are at most k.

Time complexity: O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // O(n) O(n)
        
        if (nums == null || nums.length == 0 || k < 0) {
            return false;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        
        // Check whether having the same key, but the value is different
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            
            map.put(nums[i], i);
        }
        
        return false;
    }
}

Followup:
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Analysis:

 

Leetcode 136. Single Number

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?

Analysis:

Bit manipulation. Based on the rules that a ^ b ^ a = b,  0 ^ b = b. So we can go through the whole array and use the xor to get the only one.

Time complexity: O(n)

Space complexity: O(1)

Below is the code:

public class Solution {
    public int singleNumber(int[] nums) {
        // O(n) O(1)
        // a ^ b ^ a = b,  0 ^ b = b
        
        // Corner case
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= nums[i];
        }
        
        return result;
    }
}

Leetcode 1, 167 & 170 Two Sum I, II && III

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Analysis:

To get two values which the sum of them equals to the target, the brute force one is to have 2 for loop to go over the array twice. This could take O(n^2).

So consider how to get an value very quick, we can have hashtable, which can quickly get the value in nearly O(1).

So basically, what we can do it to put all values in a hash table. Then go over it again to find another value.

Note: here we use the value as key and the index as the value.

Time complexity: O(n)

Space complexity: O(n)

The code is below:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Hashtable O(n) O(n)
        
        // Corner case
        if (nums == null || nums.length == 0) {
            return null;
        }
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // number as key, index as value
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp) && map.get(temp) != i) {
                return new int[] {i, map.get(temp)};
            }
        }
        
        return null;
    }
}

 

Follow up:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis:

Sorted array? Very familiar? Yes, binary search.

Also we can use another powerful method called two pointers: we can have a start and end. If start + end = target, then return them. If start + end < target, we know that start is small, so we add start by 1. Otherwise reduce the end by 1.

Time complexity: O(n)

Space complexity: O(1)

The code is below:

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        //Two pointers O(n) O(1)
        
        // Corner case
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        
        int start = 0;
        int end = numbers.length - 1;
        
        while (start < end) {
            if (numbers[start] + numbers[end] == target) {
                return new int[] {start + 1, end + 1};
            } else if (numbers[start] + numbers[end] < target) {
                start++;
            } else {
                end--;
            }
        }
        return null;
    }
}

Followup:
Design and implement a TwoSum class. It should support the following operations: add and find.

add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Analysis:

This is more like a design problem. So we can use the similar method to have a hash table to store the value. For adding, we can use map.put() and for finding, we can go through the entrySet and find another value.

Note: for special case where we have multiple values to be the same, like 0, 0, 0 if we want to find 0, it also should return true. So we should add a condition that, if i == j then the occurrence should be larger than 1.

Time complexity: O(n)

Space complexity: O(n)

The code is below:

public class TwoSum {

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

    // Add the number to an internal data structure.
	public void add(int number) {
	    if (map.containsKey(number)) {
	        map.put(number, map.get(number) + 1);
	    } else {
	        map.put(number, 1);
	    }
	}

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // Find i + j == value
            int i = entry.getKey();
            int j = value - i;
            
            // special case when i == j 
            if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {
                return true;
            }
        }
        return false;
    }
	
}


// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);

Leetcode 1 Two Sum

Leetcode 1 Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Analysis:

The first problem in Leetcode!!!

Brute force method:

Use two loops, go find int x and then find the value of target – x. This could lead to O(n^2) time complexity.

Alternative method – Hashtable:

Use key for numbers in the array, and the index as the value. Add every number into the hashtable and its index as the value. If found a pair, set their index into the return array.

Time complexity: O(n)

Space complexity: O(n)

As we need to go through the whole array once, so it’s O(n), while look up in hashtable is O(1).

Note: we can not use two pointers here, as we need to find the index and the numbers is not sorted.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        // method 1: hashtable O(n), O(n)
        if (nums == null || nums.length == 0) {
            return null;
        }
        
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                break;
            }
            map.put(nums[i], i);
        }
        
        return result;

     // method 2: two pointers O(nlogn + n) = O(nlogn)
     // can not use two pointers here, as we need to sort the array and can not find the index.
    }
}