Posts

Showing posts with the label Divide and Conquer

[LeetCode] 169. Majority Element

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. Thought process: Brute force solution is trivial. Iterate through the array. Keep track of a majority element candidate and its count. Increment count if current number == majority and decrement count otherwise. Reset majority element and count if count == 0. At the end, if there's a majority element, count > 0. count is essentially count of majority elements - count of other numbers. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int majorityElement ( int [] num ) { int majority = num [ 0 ]; int count = 1 ; for ( int i = 1 ; i < num . length ; i ++){ if ( count == 0 ) { count ++; ...

[LeetCode] 282. Expression Add Operators

Given a string that contains only digits  0-9  and a target value, return all possibilities to add  binary  operators (not unary)  + ,  - , or  * between the digits so they evaluate to the target value. Examples:  "123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> [] Thought process: Divide and conquer. Backtracking. Iterate through all sub-string combinations. Add operators between numbers. Put path into result list if the calculated result equals target. The characters may be combined to form a multi-digit number. So I need to iterate through all sub-string combinations. Note that the string "0d" cannot be simplified to d (0 can't be dropped). So skip the sub-strings that start with a 0. Solution: 1 2 3 4 ...

[LeetCode] 215. Kth Largest Element in an Array

Find the  k th 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. Thought process: Divide and conquer. Quick select. Use the partition algorithm from quick sort to sort the array in descending order. After partitioning, there are three cases for the pivot: Pivot == k: found the kth largest element. Pivot < k: keep searching on the right side. Pivot > k: keep searching on the left side. Solution 1 (quick select): 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 class Solution { private Random random = new Random (); public int findKthLargest ( int [] nums , int k ) { return partition ( nums , k , 0 , nums . length - 1 ); } ...

[LeetCode] 218. The Skyline Problem

Image
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are  given the locations and height of all the buildings  as shown on a cityscape photo (Figure A), write a program to  output the skyline  formed by these buildings collectively (Figure B).   The geometric information of each building is represented by a triplet of integers  [Li, Ri, Hi] , where  Li  and  Ri  are the x coordinates of the left and right edge of the ith building, respectively, and  Hi  is its height. It is guaranteed that  0 ? Li, Ri ? INT_MAX ,  0 < Hi ? INT_MAX , and  Ri - Li > 0 . You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. For instance, the dimensions of all buildings in Figure A are recorded as:  [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] . The output is a list ...

[LeetCode] 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array  [-2,1,-3,4,-1,2,1,-5,4] , the contiguous subarray  [4,-1,2,1]  has the largest sum =  6 . click to show more practice. More practice: If you have figured out the O( n ) solution, try coding another solution using the divide and conquer approach, which is more subtle. Thought process: Iterate through the array and keep track of the maximum subarray that ends at current index. Update the global max based on current rolling max. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 public class Solution { public int maxSubArray ( int [] nums ) { int max = Integer . MIN_VALUE ; int maxEndingHere = 0 ; for ( int num : nums ) { maxEndingHere = Math . max ( maxEndingHere + num , num ); max = Math . max ( max , maxEndingHere ); ...

[LeetCode] 23. Merge k Sorted List

Merge  k  sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Thought process: Algorithm 1: Divide and conquer. Break k lists into pairs and merge a pair at a time. Algorithm 2: Use a heap. At the start, offer the first element of each list into the heap. While the heap is not empty, poll the first element from it, and offer first.next into the heap. Solution 1 (Divide and conquer): 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 51 52 53 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists ( ListNode [] lists ) { if ( lists . length == 0 ) { return null ; } return mergeKLists ( lists , 0 , lists . l...

[LeetCode] 4. Median of Two Sorted Arrays

There are two sorted arrays  nums1  and  nums2  of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 Thought process: If the arrays are combined into one sorted array, the number we're looking for will be at index (m + n) / 2, or ((m + n) / 2 - 1 + (m + n) / 2) / 2. The numbers before the median in the combined array will consist of some numbers from nums1, and some numbers from nums2. Assume half of the (m + n) / 2 numbers are from nums1, and the other half is from nums2. Say i = (m + n) / 2, we compare nums1[i / 2] with nums2[i / 2]. If nums1[i / 2] < nums2[i / 2], then we're sure that the numbers before nums1[i / 2] will not contain the median that we're looking for. To avoid off-by-one errors and stack overflow, we'll ...

[LeetCode] 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an  m  x  n  matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. For example, Consider the following matrix: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] Given  target  =  5 , return  true . Given  target  =  20 , return  false . Thought process: Because the rows and columns are sorted, the numbers at the top-right and bottom-left corners are likely to be approximately the median of the matrix. So we borrow the idea of binary search. Let's start at the top-right corner. Compare the number at the top-right corner with the target. If number < target, we know that target cannot be in this row because number is the largest number in this row...