253 LeetCode Java: Meeting Rooms – Medium

Problem:

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

Thoughts:

We still need to sort the intervals by start time in order to make things easier.
A very straightforward way is to have a List of Interval and stored as the occupied interval of a room. And the size of the List will be the number of rooms required.

Because the start time is in increasing order, so that when you found a meeting that needs to be put into one room, it doesn't matter which available room to put in. E.g. if there are three rooms can support a meeting at 1pm and the end time of three rooms are 9 am , 10 am and 11 am. We can arrange this meeting at 1pm to any of the three. Because we know the next (if has next) meeting will start later than 1pm. No matter where we put 1pm meeting, we will have only two rooms available for the later ones.

Because we only care about the end time of a room, so actually we can use a min-heap to keep track of end time so that we don't need to iterate over the list of rooms. Because for a heap. add takes O(logn) in worse case and peek takes O(1) which would be mush faster.

Note that in Java, PriorityQueue is default to be min-heap. If we want to use max-heap, we have to use PriorityQueue pq = new PriorityQueue(11, Collections.reverseOrder());.

Solutions:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    class IntervalComparator implements Comparator<Interval> {
        @Override
        public int compare(Interval i1, Interval i2) {
            return i1.start - i2.start;
        }
    }
    public int minMeetingRooms(Interval[] intervals) {
        List<Interval> rooms = new LinkedList<Interval>();
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new IntervalComparator());
        rooms.add(intervals[0]);
        for (int i = 1; i < intervals.length; i ++) {
            boolean found = false;
            for (Interval inter:rooms) {
                if (intervals[i].start >= inter.end) {
                    inter.end = intervals[i].end;
                    found = true;
                    break;
                }
            }
            if (found == false) {
                rooms.add(intervals[i]);
            }
        }
        return rooms.size();
    }
}
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    class IntervalComparator implements Comparator<Interval> {
        @Override
        public int compare(Interval i1, Interval i2) {
            return i1.start - i2.start;
        }
    }
    public int minMeetingRooms(Interval[] intervals) {
        PriorityQueue<Integer> end = new PriorityQueue<Integer>();
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new IntervalComparator());
        end.add(intervals[0].end);
        for (int i = 1; i < intervals.length; i ++) {
            if (intervals[i].start >= end.peek()) {
                end.poll();
            }
            end.add(intervals[i].end);
        }
        return end.size();
    }
}

252 LeetCode Java: Meeting Rooms – Easy

Problem:

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

Thoughts:

We can solve this problem easily by sorting the Intervals. But there is no custom comparator for it so that we need to create one.

We want to sort the Interval by the start time, then if a person can attend all meetings, the start time of a meeting must be after the end time of the previous one.

Solutions:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    class IntervalComparator implements Comparator<Interval> {
        @Override
        public int compare(Interval i1, Interval i2) {
            if (i1.start > i2.start) {
                return 1;
            }
            else if (i1.start < i2.start) {
                return -1;
            }
            else {
                return 0;
            }
        }
    } 
    public boolean canAttendMeetings(Interval[] intervals) {
        Arrays.sort(intervals, new IntervalComparator());
        for (int i = 1; i < intervals.length; i ++) {
            if (intervals[i].start < intervals[i-1].end) {
                return false;
            }
        }
        return true;
    }
}

251 LeetCode Java: Count Univalue Subtrees – Medium

Problem:

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Hint:

  1. How many variables do you need to keep track?

 

Thoughts:

A straightforward way is to flatten the 2D array into a 1D array in the constructor, then everything is easy. But this is not efficient.

When can use two Integer to represent the current index in the 2D array, and it starts with 0 and 0. We need to update the index when we call next() and hasNext().

Actually by using two Iterator is making the problem much easier.
It’s similar to two Integer index, we might need to update the two Iterator when we call next() and hasNext().
E.g [[1],[],[2,3]].

Solutions:

public class Vector2D implements Iterator<Integer> {
    Iterator<List<Integer>> vi;
    Iterator<Integer> hi;
    public Vector2D(List<List<Integer>> vec2d) {
        vi = vec2d.iterator();
    }
    private void check() {
        if (hi == null || !hi.hasNext()) {
            while (vi.hasNext()) {
            hi = vi.next().iterator();
                if (hi.hasNext()) {
                    return;
                }
            }
        }
    }
    @Override
    public Integer next() {
        check();
        return hi.next();
    }

    @Override
    public boolean hasNext() {
        check();
        if (hi == null) {
            return false;
        }
        return hi.hasNext();
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */

250 LeetCode Java: Count Univalue Subtrees – Medium

Problem:

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

Thoughts:

This problem can be solved by using recursion easily.
We will need a function to return if a tree is having all the same values. Say the function is isUni(), then the condition for a tree to be a univalue tree is that node.left and node.right are both univalue tree and they have the same val with the node.

Also we will need a counter to keep the numbers of univalue subtree. In the solution below, I am using a class property. If not, we can use a TreeNode variable and pass it into isUni() so that each time inside of isUni function, it’s modifying the same variable.

Solutions:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) {
            return 0;
        }
        count = 0;
        isUni(root);
        return count;
    }
    private boolean isUni(TreeNode node) {
        if (node == null) {
            return true;
        }
        boolean left = isUni(node.left);
        boolean right = isUni(node.right);
        if (left == true && right == true) {
            if (node.left != null && node.left.val != node.val) {
                return false;
            }
            if (node.right != null && node.right.val != node.val) {
                return false;
            }
            count ++;
            return true;
        }
        return false;

    }
}

249 LeetCode Java: Group Shifted Strings – Easy

Problem:

Given a string, we can “shift” each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep “shifting” which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
A solution is:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Thoughts:

The idea is to find what’s in common for those strings that belongs to the same shifting sequence.
In order to shift one string, we increase each of the letter by 1, which means the difference between each letter keeps the same. Say for acef, the different is 2, 1, 1, when you shift, it becomes bdfg 2, 1, 1. So we just need to calculate this sequence.
The original idea is to store that in a string because it’s easy to compare string to be equal. I tried with this solution and it passed. But I think it’s better to avoid this because 121 can be interpreted into 12, 1 or 1, 21. So we still use string but each char we store the difference, because the different is at most 25.

Solutions:

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        HashMap<String, List<String>> data = new HashMap<String, List<String>>();
        for (int i = 0; i < strings.length; i ++) {
            String c = code(strings[i]);
            if (!data.containsKey(c)) {
                data.put(c, new LinkedList<String>());
            }
            data.get(c).add(strings[i]);
        }
        List<List<String>> result = new LinkedList<List<String>>();
        for (String s:data.keySet()) {
            result.add(data.get(s));
        }
        return result;
    }
    private String code(String s) {
        String result = "";
        for (int i = 1; i < s.length(); i ++) {
            int tmp = (s.charAt(i) - s.charAt(i-1) + 26 ) % 26;
            result += (char)tmp;
        }
        return result;
    }
}

248 LeetCode Java: Different Ways to Add Parentheses – Hard

Problem:

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

Thoughts:

This is an extension of version II. See 247 LeetCode Java: Strobogrammatic Number II – Medium.
With the solution we have in version II, we can easily get all the strobogrammatic string that has length of n.
We just need to only count the number that meets criteria low <= num <= high.
The easiest way is to get all the strobogrammatic strings, that has length of low.length() to high.length(). And iterate over every of them and check if they meets the criteria above.

The solution below is adding some more if to avoid unnecessary iteration. It doesn't affect the running time in O. Because in order to generate a list of n, it needs O(n), and if we add one more iteration on the list the time stays in O(n).

Solutions:

public class Solution {
    public int strobogrammaticInRange(String low, String high) {
        if (low.length() > high.length() || (low.length() == high.length() && low.compareTo(high) == 1)) {
            return 0;
        }
        int n1 = low.length();
        int n2 = high.length();
        int count = 0;
        if (n1 == n2) {
            List<String> tmp = findStrobogrammatic(n1);
            for (String s:tmp) {
                if (s.compareTo(low) >= 0 && s.compareTo(high) <= 0) {
                    count ++;
                }
            }
            return count;
        }
        List<String> tmp = findStrobogrammatic(n1);
        for (String s:tmp) {
            if (s.compareTo(low) >= 0) {
                count ++;
            }
        }
        tmp = findStrobogrammatic(n2);
        for (String s:tmp) {
            if (s.compareTo(high) <= 0) {
                count ++;
            }
        }
        for (int i = n1 + 1; i < n2; i ++) {
            int size = findStrobogrammatic(i).size();
            count += size;
        }
        return count;

    }
    //from solution of version II problem
    private List<String> findStrobogrammatic(int n) {
        HashMap<Character, Character> map = new HashMap<Character, Character>();
        map.put('1','1');
        map.put('0','0');
        map.put('8','8');
        map.put('6','9');
        map.put('9','6');
        List<String> result = new LinkedList<String>();
        if (n <= 0) {
            return result;
        }

        result.add("1");
        result.add("0");
        result.add("8");
        if (n == 1) {
            return result;
        }
        if (n % 2 != 0) {
            n --;
        }
        else {
            result.clear();
            result.add("");
        }
        while (n > 1) {
            List<String> newresult = new LinkedList<String>();
            for (String s:result) {
                for (Character c:map.keySet()) {
                    if (n != 2 || c != '0') {
                        newresult.add(c + s + map.get(c));
                    }
                }
            }
            result = newresult;
            n = n - 2;
        }     
        return result;
    }
}