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 92 & 206. Reverse Linked List I & II

Reverse a singly linked list.

click to show more hints.

Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?

Analysis:

For iteration, we need to have a prev and next node for temporal save.

For recursive,

Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let’s assume the list is: n₁ → … → n_k-1 → n_k → n_k+1 → … → n_m → Ø

Assume from node n_k+1 to n_m had been reversed and you are at node n_k.

n₁ → … → n_k-1 → n_k → n_k+1 ← … ← n_m

We want n_k+1’s next node to point to n_k.

So, n_k.next.next = n_k

Time complexity: O(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; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return null;
        }
        
        // iteration
        ListNode current = head;
        ListNode prev = null;
        ListNode next;
        
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
        
        // recursive
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        
        return p;
    }
}

Followup:
Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Analysis:
Go through the list and find the position before m. Then start from m, reverse the n-m nodes like reverse linked list.

Time complexity: O(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; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // O(n)
        
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        dummy.next = head;
        
        // Find the position before the reverse start
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }
        
        // Reverse the n - m nodes
        ListNode cur = prev.next;
        for (int i = 0; i < n - m; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        
        return dummy.next;
    }
}

Leetcode 237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4after calling your function.

Analysis:

Very intuitive method.

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        // O(1)
        
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Leetcode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?

2. What are all the possible results?

3. How do they occur, periodically or randomly?

4. You may find this Wikipedia article useful.

Analysis:

Go to the link and find the common solutions for digital root: https://en.wikipedia.org/wiki/Digital_root

dr(n) = 1 + (n – 1) mod 9

原理10 % 9 或者 100 % 9都等于 1 % 9。举个例子n = abc = a  * 100 + b * 10 + c，那么 (a*100 + b * 10 + c) % 9 = (a + b + c) % 9。由此n == 0时，result = 0， n % 9 == 0时， 说明a + b + c = 9，我们返回9，对于其他数字， (a + b + c)等于res % 9。

Code is below:

public class Solution {
    public int addDigits(int num) {
        // O(1)
        return 1 + (num - 1) % 9;
    }
}

Leetcode 169 & 229. Majority Element I & II

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Analysis:

Use hash table.

Time complexity: O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public int majorityElement(int[] nums) {
        // O(n) O(n)
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {             if (map.containsKey(nums[i])) {                 map.put(nums[i], map.get(nums[i]) + 1);             } else {                 map.put(nums[i], 1);             }         }                  for (int item : map.keySet()) {             if (map.get(item) > (nums.length / 2)) {
                return item;
            }
        }
        
        return -1;
    }
}

Followup:
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?
Do you have a better hint? Suggest it!

Analysis:

Hash table

Time complexity: O(n)
Space complexity: O(n)

Code is below:

public class Solution {
    public List majorityElement(int[] nums) {
        // O(n) O(n)
        
        Map<Integer, Integer> map = new HashMap<>();
        List result = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {             if (map.containsKey(nums[i])) {                 map.put(nums[i], map.get(nums[i]) + 1);             } else {                 map.put(nums[i], 1);             }         }                  for (int item : map.keySet()) {             if (map.get(item) > (nums.length / 3)) {
                result.add(item);
            }
        }
        
        return result;
    }
}

Leetcode 15, 16 & 259. 3Sum 3Sum Closest & 3Sum Smaller

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Analysis:

It’s very similar to the two sum with sorted array. Basically we need to sort the array, then use two pointers method to get the result.

Note: if we encounter duplicates, then we need to skip them and continue.

Time complexity: O(n^2)

Space complexity: O(n)

Below is the code:

public class Solution {
    public List<List> threeSum(int[] nums) {
        // Two pointers O(n^2) O(n)
        // Sort the array firstly, then use two pointers
        
        List<List> result = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            // To skip duplicates, like [0, 0, 0, 0]
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // Two sum two pointers below
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum == 0) {
                    List temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    result.add(temp);
                    left++;
                    right--;
                    
                    //To skip the duplicates
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
}

Followup:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Analysis:

The only difference here is to have a value of closest, we can initialize it to be the first three values then update it.

Time complexity: O(n^2)

Space complexity: O(1)

The code is below:

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // Two pointers O(n^2) O(1)
        
        if (nums == null || nums.length < 3) {
            return 0;
        }
        
        Arrays.sort(nums);
        int closest = nums[0] + nums[1] + nums[2];
        
        for (int i = 0; i < nums.length - 2; i++) {
            // To skip duplicates, like 0, 0, 0, 0
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(closest - target)) {
                    closest = sum;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return closest;
    }
}

Followup:

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n²) runtime?

Analysis:

very similar to 3Sum, only difference is to update the count that satisfies the condition. Note that the count will be updated to be right – left.

Time complexity: O(n^2)

Space complexity: O(1)

The code is below:

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        // Two pointers O(n^2) O(1)
        
        if (nums == null || nums.length < 3) {
            return 0;
        }
        
        Arrays.sort(nums);
        
        int count = 0;
        
        for (int i = 0; i < nums.length - 2; i++) {
            // Below is two sum
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < target) {
                    // There're right - left pairs satisfied the condition
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return count;
    }
}

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);