MrainW's Home

All things come to those who wait!

0%

Posted on In ,
Symbols count in article: 989 Reading time ≈ 1 mins.

Question

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

https://leetcode.com/problems/add-two-numbers-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while(l1 != null){
            stack1.push(l1.val);
            l1=l1.next;
        }
        while(l2 != null){
            stack2.push(l2.val);
            l2= l2.next;
        }
        ListNode res = null;
        int carry = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty() || carry != 0){
            int val1 = stack1.isEmpty() ? 0 : stack1.pop();
            int val2 = stack2.isEmpty() ? 0 : stack2.pop();
            int sum = val1 + val2 + carry;
            ListNode cur = new ListNode(sum % 10);
            carry = sum / 10;
            cur.next = res;
            res = cur;
        }
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 807 Reading time ≈ 1 mins.

Question

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

https://leetcode.com/problems/add-two-numbers/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode dummy = new ListNode(-1), cur = dummy;
        while(l1!=null || l2 != null){
            int sum = carry;
            if(l1 != null){
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                sum += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            carry = sum / 10;
        }
        if (carry > 0) cur.next = new ListNode(carry);
        return dummy.next;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.5k Reading time ≈ 1 mins.

Question

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

https://leetcode.com/problems/reverse-nodes-in-k-group/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // Save the previous reversed pointer in prev 
        //and in wach iteration use prev.next to set the previous ptr 
        //to the current reversed.
        ListNode tempNode = new ListNode(0);
        tempNode.next = head;
        ListNode tempHead = head;
        ListNode prev = tempNode;
        while(tempHead!=null){
            // Starting of each reversed list, 
            //it will become the last after reversing
            ListNode klast = tempHead;
            int num = k;
            // Jump k 
            while(num>0 && tempHead!=null){
                tempHead = tempHead.next;
                num--;
            }
            // If cannot reverse
            if(num!=0) {
                prev.next = klast;
                break;
            }
            // start of each reversed group
            ListNode kstart = reverse(klast,k);
            
            // Use previous's next to point to curr reversed
            prev.next = kstart;
            // Set prev to current rev end.
            prev = klast; 
        }
        return tempNode.next;
        
    }
    
    // Standard reverse code
    public ListNode reverse(ListNode head, int k){
        ListNode prev = null;
        while(head!=null && k>0){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
            k--;
        }
        return prev;
    }
    
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 410 Reading time ≈ 1 mins.

Question

Given the head of a singly linked list, reverse the list, and return the reversed list.

https://leetcode.com/problems/reverse-linked-list/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 732 Reading time ≈ 1 mins.

Question

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

https://leetcode.com/problems/reverse-linked-list-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode fakeHead = new ListNode(-1);
        fakeHead.next = head;
        ListNode prev = fakeHead;
        ListNode cur = fakeHead.next;
        int i = 1;
        while(i < left){
            prev = cur;
            cur = cur.next;
            i++;
        }
        ListNode node = prev;
        while (i++ <= right){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        node.next.next = cur;
        node.next = prev;
        return fakeHead.next;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 731 Reading time ≈ 1 mins.

Question

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

https://leetcode.com/problems/combinations

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, new ArrayList<>(), n, k, 1);
        return res;
    }
    private void dfs(List<List<Integer>> res, List<Integer> level, int n, int k, int index){
        if (level.size() == k) res.add(new ArrayList<>(level));
        else{
            for (int i = index; i <= n; i++){
                level.add(i);
                dfs(res, level, n, k, i + 1);
                level.remove(level.size() - 1);
            }
        }
    }
}

Complexity:

Time complexity: O(C(n, k))

Space complexity: O(k)

Posted on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

Question

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

https://leetcode.com/problems/palindrome-partitioning/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<List<String>> partition(String s) {
   List<List<String>> list = new ArrayList<>();
   backtrack(list, new ArrayList<>(), s, 0);
   return list;
}

public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
   if(start == s.length())
      list.add(new ArrayList<>(tempList));
   else{
      for(int i = start; i < s.length(); i++){
         if(isPalindrome(s, start, i)){
            tempList.add(s.substring(start, i + 1));
            backtrack(list, tempList, s, i + 1);
            tempList.remove(tempList.size() - 1);
         }
      }
   }
}

public boolean isPalindrome(String s, int low, int high){
   while(low < high)
      if(s.charAt(low++) != s.charAt(high--)) return false;
   return true;
} 
/*
    Time: O(n*2^n), T(n) = 2T(n-1) + P(n)
    Space: O(n*2^n)
*/

Complexity:

Time complexity: O(n*2^n)

Space complexity: O(n*2^n)

Posted on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

Question

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

https://leetcode.com/problems/combination-sum-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
    
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{
        for(int i = start; i < nums.length; i++){
            if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i + 1);
            tempList.remove(tempList.size() - 1); 
        }
    }
} 
/*
    Time: O(k * C(n, k)), O(n*2^n)
    Space: O(n)
*/

Complexity:

Time complexity: O(n*2^n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.3k Reading time ≈ 1 mins.

Question

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

https://leetcode.com/problems/combination-sum/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
   public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
        if(remain < 0) return;
        else if(remain == 0) list.add(new ArrayList<>(tempList));
        else{ 
            for(int i = start; i < nums.length; i++){
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}
/*
    Time: O(k * C(n, k))， O(n*2^n)
    Space: O(n)
*/

Complexity:

Time complexity: O(n*2^n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 973 Reading time ≈ 1 mins.

Question

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

https://leetcode.com/problems/permutations-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if(tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for(int i = 0; i < nums.length; i++){
            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
            used[i] = true; 
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, used);
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}
/*
    Time: O(N!)
    Space: O(N)
*/

Complexity:

Time complexity: O(N!)

Space complexity: O(n)