MrainW's Home

All things come to those who wait!

0%

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

Question

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    //time complexity logn
    public double myPow(double x, int n) {
        if ( x == 0 || x == 1) return x;
        if (n < 0) return 1 / pow(x, -n);
        return pow(x, n);
    }
    private double pow(double x, int n){
        if (n == 0) return 1;
        double y = pow(x, n / 2);
        if (n % 2 == 0) return y * y;
        else return y * y * x;
    }
}

Complexity:

Time complexity: O( logn)

Space complexity: O(logn)

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

Question

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

https://leetcode.com/problems/majority-element/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0, candidate = 0;
        for (int num : nums){
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(1)

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

Question

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

https://leetcode.com/problems/implement-trie-prefix-tree/

  • 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
class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c-'a']==null) node.children[c-'a'] = new TrieNode();
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a']==null) return false;
            node = node.children[c-'a'];
        }
        return node.isWord;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c: prefix.toCharArray()){
            if(node.children[c-'a']==null) return false;
            node = node.children[c-'a'];
        }
        return true;
    }
    
class TrieNode {
    TrieNode[] children;
    boolean isWord;
    public TrieNode(){
        children = new TrieNode[26];
    }
}
}

Complexity:

Time complexity: O( n)

Space complexity: O(1)

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

Question

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

https://leetcode.com/problems/remove-covered-intervals/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) ->
                     (a[0] == b[0] ? b[1] - a[1] : a[0] -b[0]));
        int count = 0, cur =0;
        for (int[] i : intervals)
            if (cur < i[1]){
                cur = i[1];
                count++;
            }
        return count;
    }
}

Complexity:

Time complexity: O( nlogn)

Space complexity: O(1)

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

Question

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

https://leetcode.com/problems/non-overlapping-intervals/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int count = 0, end = Integer.MIN_VALUE;
        for (int[] cur : intervals){
            if (end <= cur[0]) end = cur[1];
            else count++;
        }
        return count;
    }
}

Complexity:

Time complexity: O( nlogn)

Space complexity: O(1)

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

Question

A set of real numbers can be represented as the union of several disjoint intervals, where each interval is in the form [a, b). A real number x is in the set if one of its intervals [a, b) contains x (i.e. a <= x < b).

You are given a sorted list of disjoint intervals intervals representing a set of real numbers as described above, where intervals[i] = [ai, bi] represents the interval [ai, bi). You are also given another interval toBeRemoved.

Return the set of real numbers with the interval toBeRemoved removed from intervals. In other words, return the set of real numbers such that every x in the set is in intervals but not in toBeRemoved. Your answer should be a sorted list of disjoint intervals as described above.

https://leetcode.com/problems/remove-interval/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> res = new ArrayList<>();
        for(int[] i : intervals){
            if (i[1] <= toBeRemoved[0] || i[0] >= toBeRemoved[1]){
                res.add(Arrays.asList(i[0], i[1]));
            } else{
                if (i[0] < toBeRemoved[0])
                    res.add(Arrays.asList(i[0], toBeRemoved[0]));
                if (i[1] > toBeRemoved[1])
                    res.add(Arrays.asList(toBeRemoved[1], i[1]));
            }
        }
        return res;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

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

Question

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

https://leetcode.com/problems/insert-interval/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        for (int[] cur : intervals)
            if (newInterval == null || cur[1] < newInterval[0]) res.add(cur);
            else if (cur[0] > newInterval[1]){
                res.addAll(List.of(newInterval, cur));
                newInterval = null;
            } else {
                newInterval[0] = Math.min(newInterval[0], cur[0]);
                newInterval[1] = Math.max(newInterval[1], cur[1]);
            }
        if (newInterval != null) res.add(newInterval);
        return res.toArray(new int[res.size()][]);
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

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

Question

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

https://leetcode.com/problems/merge-intervals/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if (intervals == null || intervals.length == 0) return new int[0][];
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[] cur = intervals[0];
        for (int[] next : intervals){
            if (cur[1] >= next[0]) cur[1] = Math.max(cur[1], next[1]);
            else{
                res.add(cur);
                cur = next;
            }
        }
        res.add(cur);
        return res.toArray(new int[0][]);
    }
}

Complexity:

Time complexity: O( nlogn)

Space complexity: O(n)

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

Question

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

https://leetcode.com/problems/meeting-rooms-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int res = 0;
        List<int[]> list = new ArrayList<>();
        for (int[] interval : intervals){
            list.add(new int[]{interval[0], 1});
            list.add(new int[]{interval[1], -1});
        }
        Collections.sort(list, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] -b[0]);
        int count =0;
        for (int[] point: list){
            count += point[1];
            res = Math.max(res, count);
        }
        return res;
    }
}

Complexity:

Time complexity: O( nlogn)

Space complexity: O(n)

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

Question

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

https://leetcode.com/problems/meeting-rooms/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        if (intervals.length == 1) return true;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i-1][1]) return false;
        }
        return true;
    }
}

Complexity:

Time complexity: O( nlogn)

Space complexity: O(1)