@sgoogs All are O(n)
Chidong
@Chidong
Posts made by Chidong

RE: Short Java DP Solution with Explanation
@pbs It is just a base case for future operations.

RE: Short Java DP Solution with Explanation
@pbs If you use none number from the array, your sum must be 0. You have 1 way to do it. So dp[0+sum] = 1.

RE: Super Short & Easy Java O(n) Solution
@shawngao Yes! I blame auto correction LOL

RE: Super Short & Easy Java O(n) Solution
Just for the sake of fun, don't think any solution can be shorter than this lol:
public class Solution { public int findMinMoves(int[] machines) { int total = 0; for(int i: machines) total+=i; if(total%machines.length!=0) return 1; int avg = total/machines.length, cnt = 0, max = 0; for(int load: machines) max = Math.max(Math.max(max, Math.abs(cnt+=loadavg)), loadavg); return max; } }

RE: AC Java solution using min heap
Same idea but shorter
public class Solution { public int minMeetingRooms(Interval[] intervals) { if(intervals==null  intervals.length==0) return 0; Arrays.sort(intervals, (a,b)>(a.start  b.start)); PriorityQueue<Integer> pq = new PriorityQueue<>(); for(Interval i: intervals){ if(pq.size()>0 && pq.peek()<=i.start) pq.poll(); pq.add(i.end); } return pq.size(); } }
Don't need to store Interval in pq. Only storing the end times is fine.

RE: Super Short & Easy Java O(n) Solution
@swatisaoji1 I didn't find any similar problems/solutions. I just tried a couple of different inputs, and figured out the pattern. There are mainly two scenarios:
(1) the "gain/lose" array: [2,2,2,2], because the adjacent machines can neutralize each other directly. The result comes directly from the max of the load need to be transferred of a machines. In this case, it is 2. Easy.
(2) the "gain/lose" array: [1,7,4,4], for the 1st "1", inorder to be neutralized by a negative number, it need to climb over "7", because it cannot just do the neutralization with its neighbors. So, effectively, [1,7,4,4] equals [0,8,4,4]. Similar to (1), we can know for [0,8,4,4], we need 8 steps.
After trying some examples, we can find that keeping track of max of our array and the max of any intermediate values, while doing our neutralization process, can give us the result.
BTW, I am not a native speaker, not 100% sure if the term "gain/lose array" makes sense or not, or how about calling it "balance array" or "toBeBalanced array"? lol

RE: Super Short & Easy Java O(n) Solution
@Junjie_Wen Added some explanation. Hope it helps.

Super Short & Easy Java O(n) Solution
public class Solution { public int findMinMoves(int[] machines) { int total = 0; for(int i: machines) total+=i; if(total%machines.length!=0) return 1; int avg = total/machines.length, cnt = 0, max = 0; for(int load: machines){ cnt += loadavg; //loadavg is "gain/lose" max = Math.max(Math.max(max, Math.abs(cnt)), loadavg); } return max; } }
Let me use an example to briefly explain this. For example, your machines[] is [0,0,11,5]. So your total is 16 and the target value for each machine is 4. Convert the machines array to a kind of gain/lose array, we get: [4,4,7,1]. Now what we want to do is go from the first one and try to make all of them 0.
To make the 1st machines 0, you need to give all its "load" to the 2nd machines.
So we get: [0,8,7,1]
then: [0,0,1,1]
lastly: [0,0,0,0], done.
You don't have to worry about the details about how these machines give load to each other. In this process, the least steps we need to eventually finish this process is determined by the peak of abs(cnt) and the max of "gain/lose" array. In this case, the peak of abs(cnt) is 8 and the max of gain/lose array is 7. So the result is 8.Some other example:
machines: [0,3,0]; gain/lose array: [1,2,1]; max = 2, cnt = 0, 1, 1, 0, its abs peak is 1. So result is 2.
machines: [1,0,5]; gain/lose array: [1,2,3]; max = 3, cnt = 0, 1, 3, 0, its abs peak is 3. So result is 3. 
RE: Easy Java O(n) Solution, PreSum + HashMap
same idea
public class Solution { public int findMaxLength(int[] nums) { int[] cnt = new int[nums.length]; for(int i = 0; i<nums.length; i++){ if(i>0) cnt[i] = cnt[i1]; if(nums[i]==1) cnt[i]++; else cnt[i]; } Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); int max = 0; for(int i = 0; i<cnt.length; i++){ if(map.containsKey(cnt[i])) max = Math.max(max, i  map.get(cnt[i])); if(!map.containsKey(cnt[i])) map.put(cnt[i], i); } return max; } }