I have another idea- instead of dp...we can maintain 2 sums (prefixSum left , prefixSum right)..find the mid/cut point on where to Split - > (i), such that u want a running min (rightPrefix[i] < leftPrefix[i-1]) for all i. Then depending on the sign of rightPrefix[i] -leftPrefix[i-1], u can determine whether to discard left array or right array . To elaborate - currentDist = rigthPrefix[i] - leftPrefix[i-1]; if currentDist > 0 { //prefixRight is bigger, so consider prefixleft cutStart = 0; cutEnd = i; } else { //prefix left is bigger cutStart = i + 1; curEnd = length; } else { // this is where things become little tricky, if we know the integers are going to be always +ve, then we can greedily choose the side that has max number of elements. This is guaranteed to give max score. } Total time is O(N2)
Code for anyone wondering, Nlog(N) import bisect arr = [6,4,4,5,7,8,9] n = len(arr) pre = [0]*(n+1) for i in range(1,n+1): pre[i]+=pre[i-1]+arr[i-1] i ,j = 1, len(pre)-1 res = 0 while iop1: k-=1 left ,right = pre[k] - pre[i-1], pre[j] - pre[k] if left>right: i = k+1 res+=right else: j=k res+=left print(res)
I think we can further optimize using prefix sum Because *** there are only three scenerio where can end up to optimal answer Suppose arr[]={ a , b , c , d} Every time we divide array such that it closest to the equal first when we divide the array perfectly (where score of both is equal) Recur both the arrays Else We check with left part smaller than totSum/2 and check right part smaller than totSum/2 Max of both will be the answer
Hi Keerthi , I think we can achieve NlogN time complexity using recursive approach (Correct me if I am wrong) def max_score_Gnani(array): n = len(array) if n == 1: return 0 index = find_partition(array) array1_sum = sum(array[:index]) array2_sum = sum(array[index:]) if(array1_sum < array2_sum): return array1_sum + max_score_Gnani(array[:index]) elif(array1_sum > array2_sum): return array2_sum + max_score_Gnani(array[index:]) else: return array1_sum + max(max_score_Gnani(array[:index]) , max_score_Gnani(array[index:])) def find_partition(array): n = len(array) if n == 1: return 0 sum_array = sum(array) min_diff = sum_array index = -1 for i in range(len(array)): new_min_diff = abs(min_diff - (2 * array[i])) if min_diff > new_min_diff: min_diff = new_min_diff index = i print(index+1) return index+1 print(max_score_Gnani([5 , 5, 5,5 , 5 ,5, 5, 5,5 , 5, 5, 5, 5])) Every time we will half the array but in worst case we use two halves - if we have N worst cases - N * logN
Hi Keerti, I think first line of the score function should return 0 instead of stones[l], because when the left==right, it will contribute 0 in the score
Thank you Keerti for this wonderful mock , learning alot. Although I'm a beginner but still enjoying and trying to understand . Here is a request , Can you please bring a DSA interview with Rohit Negi (Uber) ?
Really enjoyed the interview....I was also solving up the question with Fraz and the video became more interesting when kreeti was pointing out what is wrong here think about it and I was also thinking the same.... Really enjoyed it 😊 keep making more videos like this 😌
🔥🔥🔥 O(n) solution 🔥🔥🔥 We can use binary search on prefix sums for discarding in log(n).. because prefix sum will be sorted array and balance point will be min { left of (prefix sum // 2), right of (prefix sum // 2), (prefix sum // 2)} And the total discard count will be log(n) Total complexity= O(log(2n)) + O(n) for prefix sum . O(n) in total.
Didi I am doing graduation in civil engineering but I have interest in IT Can I grow my career in IT? If yes what problems I will have to face because I don't belong to computer science and I am civil engineer
Can you please do an interview of Striver(Raj Vikramaditya) he has recently joined Google Warsaw. He has a youtube channel "Take You Forward" . It would be an honour to watch his mock interview.
Today only I stumbled upon your video and I loved it. I've always been inside an interview first time getting a taste of I watching an interview from outside and It's very enjoyable. Loved the tips appeared in between the video. So insightful. I am just enjoying how a person thinks in a live interview. Subscribed
Hi..Can't we use two pointer approach to find the balance point.i.e.increment fp when the sum till fp is less than sum till sp,and similarly decrement sp when sum till sp is less than sum till fp?
Interview was a great learning opportunity. In fact, after I went through the question once, I was sure this could be solved by partition dp, since i had recently watched a mock interview by @striver on similiar track ( Scramble Strings ). However, the first approach taken by @fraz suprised me too. But later I realised that this problem could not be solved greedily as here the local optimum cannot be guaranteed to be globally optimal. I also enjoyed the bottom up method. 😊
simple dp solution: vector prefix; int n = 0; int dp[502][502]; int fun(int i, int j) { if (i == j) { return 0; } if (dp[i][j] != -1) { return dp[i][j]; } int ans = 0; int a, b; for (int k = i; k < j; k++) { a = prefix[k + 1] - prefix[i]; b = prefix[j + 1] - prefix[k + 1]; if (a < b) { ans = max(ans, a + fun(i, k)); } else if (b < a) { ans = max(ans, b + fun(k + 1, j)); } else { ans = max(ans, a + max(fun(i, k), fun(k + 1, j))); } } dp[i][j] = ans; return ans; } int main() { prefix={}; vector nums = {6, 2, 3, 4, 5, 5}; n = nums.size(); prefix.push_back(0); int sum = 0; memset(dp, -1, sizeof(dp)); for (int i = 0; i < n; i++) { sum = sum + nums[i]; prefix.push_back(sum); } cout
Hello can anyone please tell me if I do Mca as distance education , is thery any problem while applying to faang or pbc... Like I'll be eligible to apply for those companies off campus na ??? Now after bca I'm going to start my job . so I'll have both job experience and distance degree (MCA Open)...
so many interviews present on youtube and in every interview candidate solve problem easily how is it possible ? is it fixed ?? not a fail a single time ?
seemed Like Fraz complicated the first question. Not sure if I am right here. I feel there could be easier way to solve it. 1. add all the elements in given array -25 is the sum 2. then divide it into 2 part ls 12 and 13 3. then find the sum from index 0 till the point we are close to to sum 12. 4. throw away the other part. 5. repeat this with the remaining array. Its just a suggestion you think this can work?
Not tested, but how about it? do you think any memoization requirement here? int count = 0; private int game(int[] nums, int start, int end) { if (Math.abs(start - end) == 1) { count += Math.min(nums[start], nums[end]); return count; } int max = Integer.MIN_VALUE; int newStart = -1; int newEnd = -1; for (int i = start; i < end; i++) { int leftSum = 0; for (int j = start; j max) { max = leftSum; newStart = start; newEnd = i + 1; } } else if (rightSum < leftSum) { if (rightSum > max) { max = rightSum; newStart = i + 1; newEnd = end - 1; } } else { // they are same // do both and take maximum int sameLeft = game(nums, start, i); int sameRight = game(nums, i + 1, end); if (sameLeft > sameRight) { max = leftSum; newStart = start; newEnd = i; } else { max = rightSum; newStart = i + 1; newEnd = end; } } } count += max; return game(nums, newStart, newEnd); }
