Showing posts with label Sort. Show all posts
Showing posts with label Sort. Show all posts

Wednesday, July 12, 2017

527. Word Abbreviation

Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules below.
  1. Begin with the first character and then the number of characters abbreviated, which followed by the last character.
  2. If there are any conflict, that is more than one words share the same abbreviation, a longer prefix is used instead of only the first character until making the map from word to abbreviation become unique. In other words, a final abbreviation cannot map to more than one original words.
  3. If the abbreviation doesn't make the word shorter, then keep it as original.
Example:
Input: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
Note:
  1. Both n and the length of each word will not exceed 400.
  2. The length of each word is greater than 1.
  3. The words consist of lowercase English letters only.
  4. The return answers should be in the same order as the original array.



Solution:

We start from only abbreviating 1 character and put all results into an array.

Then we go through the array and put the duplicate strings to a set and only stores the index of the original string in the list.

For these strings, we need to abbreviate one more character and to the same check.



Code:


public class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {
        int n = dict.size();
        String[] res = new String[n];
        int[] prefix = new int[n];
        for (int i = 0; i < n; i++) {
            prefix[i] = 1;
            res[i] = convert(dict.get(i), 1);
        }
        for (int i = 0; i < n; i++) {
            while (true) {
                HashSet<Integer> set = new HashSet<>();
                for (int j = i + 1; j < n; j++) {
                    if (res[i].equals(res[j])) {
                        set.add(j);
                    }
                }
                if (set.isEmpty()) {
                    break;
                }
                set.add(i);
                for (int k : set) {
                    res[k] = convert(dict.get(k), ++prefix[k]);
                }
            }
        }
        return Arrays.asList(res);
    }
    public String convert(String str, int k) {
        if (k > str.length() - 2) {
            return str;
        }
        String res = str.substring(0, k) + (str.length() - k - 1) + str.charAt(str.length() - 1);
        return res.length() < str.length() ? res : str;
    }
}

Friday, July 7, 2017

451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.



Solution:

This is a bucket sort problem.

We first count the frequency of each character and maintains a max frequency.

The size of bucket array is the max + 1.

bucket[i] denotes the character(s) who has frequency of i.

We can go through the frequency map and insert each character to the corresponding bucket.

Finally, we start from the max frequency and put all characters from non-empty buckets to the result string.

The time complexity is O(n) and the space complexity is O(n).



Code:


public class Solution {
    public String frequencySort(String s) {
        int[] map = new int[256];
        int max = 0;
        for (char c : s.toCharArray()) {
            map[c]++;
            max = Math.max(max, map[c]);
        }
        String[] bucket = new String[max + 1];
        for (int i = 0; i < 256; i++) {
            String str = bucket[map[i]];
            if (map[i] > 0) {
                bucket[map[i]] = str == null ? "" + (char) i : str + (char) i;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = max; i >= 0; i--) {
            if (bucket[i] != null) {
                for (char c : bucket[i].toCharArray()) {
                    for (int j = 0; j < i; j++) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }
}

Friday, May 26, 2017

57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].



Solution:

Since the intervals are sorted, we can do:

1. Go through the list, if an interval ends before the new interval, skip it.

2. Now we meet an interval that has overlap with the new interval. We remove it from the list, merge it with new interval.

3. We meet an interval that starts after the new interval. So we simply insert new interval before it.

The time complexity is O(n) and space complexity is O(1).



Code:


/**
 * 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 {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int i = 0;
        while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
            i++;
        }
        while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
            newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
            newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
            intervals.remove(i);
        }
        intervals.add(i, newInterval);
        return intervals;
    }
}

Thursday, May 11, 2017

324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?



Solution:

Method 1: sort

Sort the array and put corresponding elements to wiggle position.

Need auxiliary array.

The time complexity is O(nlogn) and the space complexity is O(n).



Code:


public class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            int swap = nums[i];
            nums[i++] = nums[j];
            nums[j--] = swap;
        }
        int[] res = new int[nums.length];
        int m = nums.length | 1;
        for (i = 0; i < nums.length; i++) {
            res[(1 + i * 2) % m] = nums[i];
        }
        for (i = 0; i < res.length; i++) {
            nums[i] = res[i];
        }
    }
}



Method 2: 3-way partition and virtual indexing

Find median with O(n).

In-place exchange elements and put them to wiggle positions.

The time complexity is O(n) and the space complexity is O(1).

More explanation: Step by step explanation of index mapping in Java



Code:


public class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int median = findKthLargest(nums, n / 2 + 1);
        
        int left = 0, i = 0, right = n - 1;
        while (i <= right) {

            if (nums[mapIndex(i, n)] > median) {
                exch(nums, mapIndex(left++, n), mapIndex(i++, n));
            }
            else if (nums[mapIndex(i, n)] < median) {
                exch(nums, mapIndex(right--, n), mapIndex(i, n));
            }
            else {
                i++;
            }
        }
    }
    
    public int mapIndex(int index, int n) {
        return (1 + 2 * index) % (n | 1);
    }
    
    
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k - 1);
        
        return nums[k - 1];
    }
    
    public void partition(int[] nums, int lo, int hi, int pos) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int gt = lo;
        int lt = hi;
        int i = lo;
        
        while (i <= lt) {
            if (nums[i] > v) {
                exch(nums, gt++, i++);
            }
            else if (nums[i] < v) {
                exch(nums, lt--, i);
            }
            else {
                i++;
            }
        }
        
        if (gt < pos) {
            partition(nums, gt + 1, hi, pos);
        }
        if (gt > pos) {
            partition(nums, lo, gt - 1, pos);
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int swap = nums[i];
        nums[i] = nums[j];
        nums[j] = swap;
    }
}

280. Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].



Solution:

The output array should meet these two conditions:

1. If index is odd, nums[index] >= nums[i- 1].

2. If index is even, nums[index] <= nums[i- 1].

Therefore, we go through the input array and at each index we check the above conditions.

If nums[i] does not meet the conditions, we swap it with the previous number.

By doing this, all the elements ahead of nums[i] still satisfy the conditions.

The time complexity is O(n).



Code:


public class Solution {
    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if ((i % 2 == 0 && nums[i] > nums[i - 1]) || 
                (i % 2 == 1 && nums[i] < nums[i - 1])) {
                
                int swap = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = swap;
            }
        }
    }
}

253. Meeting Rooms II

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.



Solution:

We split the input array to two arrays: one with all the start points and the other with all the end points.

Sort these two arrays.

Use two pointers point to two arrays and compare each element.

If we find start time is less than end time, we know we need one more room.

If we find start time is larger than end time, we know we can release a room

We keep a max value of the rooms we need.

The time complexity is O(nlogn) since we use sort.



Code:


/**
 * 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 {
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int maxRoom = 0;
        int room = 0;
        int i = 0;
        int j = 0;
        while (i < starts.length) {
            if (starts[i] < ends[j]) {
                room++;
                maxRoom = Math.max(maxRoom, room);
                i++;
            }
            else if (starts[i] > ends[j]) {
                room--;
                j++;
            }
            else {
                i++;
                j++;
            }
        }
        return maxRoom;
    }
}

252. Meeting Rooms

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.



Solution:

We first sort the intervals by their start.

If start equals, sort by end.

Then we go through the interval array and check the start of each interval.

If it is less than the previous interval's end, we know there is an overlap.

The time complexity is O(nlogn).



Code:


/**
 * 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 {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true;
        }
        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval x, Interval y) {
                if (x.start == y.start) {
                    return x.end - y.end;
                }
                return x.start - y.start;
            }
        });
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
}

Sunday, May 7, 2017

274. H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.



Solution:

We can use a bucket sort like algorithm to solve this problem.

We use an frequency array with n + 1 length to record the frequency of citations.

If a citation is equal or greater than n, we increment frequency[n].

Then we go through frequency array reversely and check if the suffix sum at index i is equal or larger than i. If so, we know the number of citation of i papers is equal or larger than i, which is the h-index.

The time complexity is O(n) and the space complexity is also O(n).



Code:


public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        int n = citations.length;
        int[] frequency = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {
                frequency[n]++;
            }
            else {
                frequency[citations[i]]++;
            }
        }
        int count = 0;
        for (int i = n; i >= 0; i--) {
            count += frequency[i];
            if (count >= i) {
                return i;
            }
        }
        return 0;
    }
}

Wednesday, May 3, 2017

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?



Solution:

This is a classic 3-way-partition quick-select problem.

The original code only needs subtle change to accommodate only three numbers: 0, 1, and 2.



Code:


public class Solution {
    public void sortColors(int[] nums) {
        int lt = 0;
        int gt = nums.length - 1;
        int i = 0;
        
        while (i <= gt) {
            if (nums[i] == 0) {
                exch(nums, lt++, i++);
            }
            else if (nums[i] == 2) {
                exch(nums, gt--, i);
            }
            else {
                i++;
            }
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int swap = nums[i];
        nums[i] = nums[j];
        nums[j] = swap;
    }
}

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].



Solution:

The idea is to sort the List by Interval.start. (write a comparator)

Then we go through the list and compares the start of current interval with the previous interval's end.

If the start of current interval <= end of previous interval, there is an overlap, we update the end of this overlap.

If the start of current interval > end of previous interval, we know there is no overlap and the current interval can be added to the result.

The sorting takes O(nlogn) and the merge takes O(n). So the overall time complexity is O(n).



Code:


/**
 * 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 {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return result;
        }
        
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval x, Interval y) {
                if (x.start != y.start) {
                    return x.start - y.start;
                }
                return x.end - y.end;
            }
        });
        
        result.add(intervals.get(0));
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals.get(i).start <= result.get(result.size() - 1).end) {
                result.get(result.size() - 1).end = 
                    Math.max(result.get(result.size() - 1).end, intervals.get(i).end);
            }
            else {
                result.add(intervals.get(i));
            }
        }

        return result;
    }
}

215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.



Solution:

Method 1: find kth smallest

kth largest number in array nums, is the (nums.length - k + 1)th smallest umber in the array.

And its absolute position in an sorted order is nums.length - k.

Therefore, we recursively call 3-way partition until nums[nums.length - k] is finalized.



Code:


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return -1;
        }
        
        k = nums.length - k;
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k);
        
        return nums[k];
    }
    
    public void partition(int[] nums, int lo, int hi, int pos) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int lt = lo;
        int gt = hi;
        int i = lo;
        
        while (i <= gt) {
            if (nums[i] < v) {
                exch(nums, lt++, i++);
            }
            else if (nums[i] > v) {
                exch(nums, gt--, i);
            }
            else {
                i++;
            }
        }
        
        if (lt < pos) {
            partition(nums, lt + 1, hi, pos);
        }
        if (lt > pos) {
            partition(nums, lo, lt - 1, pos);
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}



Method 2: find kth largest

Modify the 3-way partition to put larger number before pivot and smaller number after pivot.

The kth largest number is nums[k - 1] after partition.



Code:


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k - 1);
        
        return nums[k - 1];
    }
    
    public void partition(int[] nums, int lo, int hi, int pos) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int gt = lo;
        int lt = hi;
        int i = lo;
        
        while (i <= lt) {
            if (nums[i] > v) {
                exch(nums, gt++, i++);
            }
            else if (nums[i] < v) {
                exch(nums, lt--, i);
            }
            else {
                i++;
            }
        }
        
        if (gt < pos) {
            partition(nums, gt + 1, hi, pos);
        }
        if (gt > pos) {
            partition(nums, lo, gt - 1, pos);
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int swap = nums[i];
        nums[i] = nums[j];
        nums[j] = swap;
    }
}