2020 June 6 Questions
53 views
Skip to first unread message
Rudy Talukder
Jun 6, 2020, 5:00:38 PM6/6/20
to leetcod...@googlegroups.com
Runtime: 332 ms, faster than 11.28% of Python3 online submissions for Minimum Moves to Equal Array Elements.
Memory Usage: 15.3 MB, less than 6.94% of Python3 online submissions for Minimum Moves to Equal Array Elements.=
#O(N) of time = 1
#O(N) of space = 1
#O(N) of space = 1
def minMoves(self, nums: List[int]) -> int:
if not nums:
return 0
#Let final value of all numbers be x. So sum total of final array = x*n
#With m moves, (n-1) numbers are incremented by 1.initial sum=num_sum=sum(nums)
#So num_sum + m*(n-1)*1 = x*n
#And x = num_min + m , where num_min is min number of array
#num_sum +m*(n-1)=(num_min + m)*n
#num_sum + mn -m = num_min*n + mn
#Therefore, m = num_sum - num_min*n
#O(N) of time = 1
#O(N) of space = 1
num_min = min(nums)
num_sum = sum(nums)
result = num_sum - len(nums)*num_min
return result
--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
https://www.techbayarea.us/
FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/0cb3d47c-7c94-4f60-a24d-0927cbfcc021o%40googlegroups.com.
rakesh katkam
Jun 6, 2020, 5:37:53 PM6/6/20
to leetcode-meetup
def minMoves2(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
#Sort the num array first
nums.sort()
mid = len(nums) // 2 #get the middle index
midValue = nums[mid] #get the middle value
left = 0
right = len(nums) - 1
moves = 0
while left <= right:
moves += midValue - nums[left]
moves += nums[right] - midValue
left += 1
right -= 1
return moves
Abhishek Kaukuntla
Jun 7, 2020, 1:35:40 AM6/7/20
to leetcode-meetup
| 453 | Minimum Moves to Equal Array Elements | 50.0% | Easy |
class Solution {
/**
Time complexity: O(n) where n is the length of the array
Space complexity: O(1)
*/
public int minMoves(int[] nums) {
int len = nums.length;
if (len == 0 || len == 1) {
return 0;
}
// Sort the array
//Arrays.sort(nums); // Note: Do not use Arrays.sort; it's time complexity is O(n log n)
// Find the min element
int min = nums[0];
for (int num : nums) {
if (num < min) {
min = num;
}
}
// Now that we found the min; let's subtract the min from every other number in the array and keep adding the difference. That's the answer.
int diff = 0;
for (int i=0; i<len; i++) {
diff += (nums[i] - min);
}
return diff;
Abhishek Kaukuntla
Jun 7, 2020, 2:00:26 AM6/7/20
to leetcode-meetup
| 462 | Minimum Moves to Equal Array Elements II | 53.5% | Medium |
Runtime: 2 ms, faster than 97.53% of Java online submissions for Minimum Moves to Equal Array Elements II.
Memory Usage: 39.7 MB, less than 98.28% of Java online submissions for Minimum Moves to Equal Array Elements II.
class Solution {
/**
Time complexity: O(n log n) because of the Arrays.sort()
Space complexity: O(1)
*/
public int minMoves2(int[] nums) {
int len = nums.length;
if (len == 0 || len == 1) {
return 0;
}
// Sort the array
Arrays.sort(nums);
// Find the mid element
int mid = nums[len/2];
// Find the moves from every element to the mid element and add them. That's the answer
int moves = 0;
for (int num : nums) {
moves += Math.abs(mid - num);
}
return moves;
}
}
On Saturday, June 6, 2020 at 9:32:51 AM UTC-7, Daryl Wang wrote:
Tarini Pattanaik
Jun 7, 2020, 2:20:50 AM6/7/20
to leetcod...@googlegroups.com
295. Find Median from Data Stream
Runtime: 53 ms, faster than 45.38% of Java online submissions for Find Median from Data Stream.
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); //minHeap always keeps largest half numbers
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b-a); //maxHeap always keep smallest number
/** initialize your data structure here. */
public MedianFinder() {
}
public void addNum(int num) {
maxHeap.add(num);
minHeap.add(maxHeap.poll());
if (maxHeap.size() < minHeap.size()) {
maxHeap.add(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return ( maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.peek();
}
}
}
--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
https://www.techbayarea.us/
FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/341046ad-0951-48b2-93b8-6e80ce60db3bo%40googlegroups.com.
deepika panda
Jun 7, 2020, 3:04:26 PM6/7/20
to leetcode-meetup
Runtime: 51 ms, faster than 57.80% of Java online submissions for Find Median from Data Stream.
Memory Usage: 50.4 MB, less than 87.11% of Java online submissions for Find Median from Data Stream.
class MedianFinder {
PriorityQueue<Integer> maxHeap; // Store the first half elements
PriorityQueue<Integer> minHeap; // Store the second half elements
/** initialize your data structure here. */
public MedianFinder() {
maxHeap = new PriorityQueue<>((a,b) -> { return b-a ;});
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if (minHeap.size() > maxHeap.size())
maxHeap.offer(minHeap.poll());
}
public double findMedian() {
if (maxHeap.isEmpty() && minHeap.isEmpty())
return 0.0;
if (minHeap.size() == maxHeap.size())
return (double) (minHeap.peek() + maxHeap.peek())/2;
else return maxHeap.peek();
}
}
// Time complexity: O(log N)
// Space complexity: O(N)
karan alang
Jun 11, 2020, 2:37:17 AM6/11/20
to leetcode-meetup
lc453 :
def minMoves(self, nums: List[int]) -> int:
minimum = min(nums)
res = 0
for n in nums:
res += n - minimum
return res
On Saturday, June 6, 2020 at 9:32:51 AM UTC-7, Daryl Wang wrote:
karan alang
Jun 12, 2020, 2:01:31 AM6/12/20
to leetcode-meetup
lc462:
def minMoves2(self, nums: List[int]) -> int:
if not nums or len(nums) == 1: return 0
if len(nums) == 2: return abs(nums[1]-nums[0])
nums.sort()
mid = (len(nums))//2
numMoves = 0
for i in range(len(nums)):
numMoves += abs(nums[mid]-nums[i])
return numMoves
one question - whether i choose mid = len(nums)//2 or or mid = (len(nums)-1)//2 .. it passes leetcode tests,
any idea on why, and should it make a difference on the value of mid ?
deepika panda
Jun 12, 2020, 2:10:15 AM6/12/20
to leetcode-meetup
462. Minimum moves to equal array elements II
Runtime: 2 ms, faster than 97.58% of Java online submissions for Minimum Moves to Equal Array Elements II.
Memory Usage: 40.2 MB, less than 52.27% of Java online submissions for Minimum Moves to Equal Array Elements II.
Using quick select.
Time: O(n), average case.
Space: O(1)
class Solution {
public int minMoves2(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int k = nums.length/2;
int median = quickSelect(nums, 0, nums.length-1, k);
int dist = 0;
for(int num : nums) {
dist += Math.abs(median-num);
}
return dist;
}
private int quickSelect(int[] nums, int low, int high, int k) {
int partitionIndex = partition(nums, low, high);
if ( k == partitionIndex)
return nums[partitionIndex];
else if (partitionIndex < k)
return quickSelect(nums, partitionIndex + 1, high, k);
else return
quickSelect(nums, low, partitionIndex - 1, k);
}
private int partition (int[] nums, int low, int high) {
int pivot = nums[low + (high-low)/2];
swap(nums, low + (high-low)/2, high);
int i = low;
for (int j = low; j <= high; j++) {
if (nums[j] < pivot){
swap(nums, i, j);
i++;
}
}
swap(nums, i, high);
return i;
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
Daryl Wang
Jun 13, 2020, 1:28:21 AM6/13/20
to leetcode-meetup
| 453 | Minimum Moves to Equal Array Elements | 50.0% | Easy |
The way the question is posed is tricky to think about; it's easiest to approach the problem the opposite direction. Instead of incrementing every element except one, we decrement just one element. These two steps are functionally equivalent, and at this point it becomes clear that we need to change every element to match the lowest element.
The code is simple at this point:
- find the minimum element
- Go through each element and add the difference between the minimum and the element to the answer
O(n) time
O(1) space
class Solution:
def minMoves(self, nums: List[int]) -> int:
target = min(nums)
ans = 0
for num in nums:
ans += num - target
return ans
On Saturday, June 6, 2020 at 9:32:51 AM UTC-7, Daryl Wang wrote:
Daryl Wang
Jun 13, 2020, 1:45:26 AM6/13/20
to leetcode-meetup
| 462 | Minimum Moves to Equal Array Elements II | 53.5% | Medium |
The fundamental idea behind this problem is to change every element to the median of the array.
We don't want to use the average because that can be skewed by a few outlier; we rather change the outliers than adjust the rest of the array to be closer to the outliers. As an example: [1,1,1,2,100] It is better to adjust 100 down to 1 instead of having to adjust every other element to be closer to 100.
Finding the median can be done in several ways. I've taken the easy solution of sorting the array and the element at the middle, but ambitious coders can use something like quick select for O(n) average time.
O(nlog(n)) time
O(1) space (assuming sorting in place)
class Solution:
def minMoves2(self, nums: List[int]) -> int:
def median():
nums.sort()
length = len(nums)
if length % 2:
return nums[length // 2]
else:
return math.ceil((nums[length // 2] + nums[length // 2 - 1]) / 2)
target = median()
ans = 0
for num in nums:
ans += abs(target - num)
return ans
On Saturday, June 6, 2020 at 9:32:51 AM UTC-7, Daryl Wang wrote:
Daryl Wang
Jun 13, 2020, 2:02:29 AM6/13/20
to leetcode-meetup
| 295 | Find Median from Data Stream | 43.1% | Hard |
The basic idea is that we keep piles of numbers as we go along: numbers above the median and numbers lower than the median. The piles should always be the same size (or 1 off if we have an odd total number of elements). We can then find the median easily. If the total number of elements is even, then it's the average of the largest number in the lower pile and the smallest number in the upper pile. If it's odd, then it's the largest number in the lower pile if that pile has more elements, the smallest number in the upper if that pile has more elements.
For each number, we compare it to the median and put it into the matching pile. We then re-balance the piles if necessary. If the upper pile is larger, then we transfer the smallest number in that pile to the lower pile. If the lower pile is larger, then we transfer the biggest number in that pile to the upper pile.
To implement the re-balancing quickly, we use heaps. That way we can add or remove elements in log(n) time and find the min/max instantly. We use a max-heap for the lower pile and a min-heap for the upper pile.
For the follow ups:
If all the elements are between 1 and 100, then we can just keep counts of each number in an array. We find the median by iterating through the array until the count sum crosses n/2, at which point that number is the median. This caps the runtime at a constant of 100 checks at most.
If most of the elements are between 1 and 100, then we can use the same idea. The one change is that we have two extra counts: one for all numbers less than 0 and one for all numbers greater than 100. Otherwise we do the same process for finding the median: sum up counts until we hit n/2. Since the vast majority of the numbers are between 1 and 100, we know that the median will also be in that range. Therefore we don't need to know the values of the numbers below 1 and above 100, just how many of them there are.
O(nlog(n)) time
O(n) space
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.lowerHeap = []
self.upperHeap = []
def addNum(self, num: int) -> None:
median = self.findMedian()
if num > median:
heapq.heappush(self.upperHeap, num)
else:
heapq.heappush(self.lowerHeap, -num)
# Rebalance heaps if necessary
if len(self.upperHeap) > len(self.lowerHeap) + 1:
# Transfer the smallest number in upperHeap to lowerHeap
heapq.heappush(self.lowerHeap, -heapq.heappop(self.upperHeap))
if len(self.lowerHeap) > len(self.upperHeap) + 1:
# Transfer the biggest number in lowerHeap to upperHeap
heapq.heappush(self.upperHeap, -heapq.heappop(self.lowerHeap))
def findMedian(self) -> float:
# Not sure what the median of an empty list is
if not self.lowerHeap and not self.upperHeap:
return 0
elif len(self.lowerHeap) > len(self.upperHeap):
return -self.lowerHeap[0]
elif len(self.lowerHeap) < len(self.upperHeap):
return self.upperHeap[0]
else:
return (-self.lowerHeap[0] + self.upperHeap[0]) / 2
On Saturday, June 6, 2020 at 9:32:51 AM UTC-7, Daryl Wang wrote:
Promila Agarwal
Jun 13, 2020, 1:04:41 PM6/13/20
to leetcod...@googlegroups.com
Hi Daryl,
Is there a zoom link for today ?
Thanks
Promila
--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
https://www.techbayarea.us/
FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/51228ad9-c10d-4e78-86e7-6f41751c7678o%40googlegroups.com.
Daryl Wang
Jun 13, 2020, 1:07:31 PM6/13/20
to leetcode-meetup
Invite if it isn't working is:
Join Zoom Meeting
https://us04web.zoom.us/j/73714258987?pwd=RUo3V2RYczlETGhNeXpabnF1VzluZz09
Meeting ID: 737 1425 8987
Password: 2rZtG8
https://us04web.zoom.us/j/73714258987?pwd=RUo3V2RYczlETGhNeXpabnF1VzluZz09
Meeting ID: 737 1425 8987
Password: 2rZtG8
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CAPWrNBiJg-KOV11cEZW%2BinWPVwx-8AkVLjQCipxczQO%3DPoW%2B1g%40mail.gmail.com.
Daryl Wang
Jun 13, 2020, 1:49:45 PM6/13/20
to leetcode-meetup
Sorry that the meeting got cut while talking about the median. Another meeting is up at
Join Zoom Meeting
https://us04web.zoom.us/j/78210523578?pwd=OUMvZkgxWVQzTEp4UHBpcnlHa0ZuZz09
Meeting ID: 782 1052 3578
Password: 7du1Uq
https://us04web.zoom.us/j/78210523578?pwd=OUMvZkgxWVQzTEp4UHBpcnlHa0ZuZz09
Meeting ID: 782 1052 3578
Password: 7du1Uq
Reply all
Reply to author
Forward
0 new messages