Maximum Value at a Given Index in a Bounded Array | Leetcode - 1802
Vložit
- čas přidán 27. 07. 2024
- Join this channel to get access to perks:
/ @algorithmsmadeeasy
Get Discount on GeeksforGeeks courses (practice.geeksforgeeks.org/co...) by using coupon code: ALGOMADEASY
To support us you can donate
UPI: algorithmsmadeeasy@icici
Check out our other popular playlists:
Questions you might like:
✅✅✅[ Tree Data Structure] : • Tree Data Structure
✅✅✅[ Graphs Data Structure] : • Graph Data Structure
✅✅✅[ February Leetcoding Challenge] : • February Leetcoding Ch...
✅✅✅[ January Leetcoding Challenge] : • January Leetcoding Cha...
✅✅✅[ February Leetcoding Challenge] : • February Leetcoding Ch...
✅✅✅[ March Leetcoding Challenge] : • March Leetcoding Chall...
✅✅✅[ December Leetcoding Challenge] : • December Leetcoding Ch...
✅✅✅[ November Leetcoding Challenge] : • November Leetcoding Ch...
✅✅✅[ August Leetcoding Challenge] : • August LeetCoding Chal...
✅✅✅[ July Leetcoding challenges] : • July LeetCoding Challe...
✅✅✅[ June Leetcoding challenges] : czcams.com/users/playlist?list...
✅✅✅[ May Leetcoding challenges] : • May LeetCoding Challen...
✅✅✅ Cracking the Coding Interview - Unique String: • Cracking the Coding In...
Problem Link: leetcode.com/problems/maximum...
Code: github.com/Algorithms-Made-Ea...
If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful.
#coding #leetcode #programminglife #programmingisfun #programmer #tech #software #codinglife #leetcode
The nums[i] is a positive integer where i is 0 to
Hi,
Thank you for taking the time to make this detail video!
You have put in a lot of work in making this video and that deserves praise.
I am having a hard time understand how the division operator is use to calculate the remaining increment.
Is it possible you can provide another example of how to calculate the remaining increment with the division operator please?
Timestamp 13:12
Never Give Up,
Thank you, you helped me a lot.
I got the unoptimized solution before watching your video and was going insane about the TLE and didn't know how to improve it :P
Glad to hear !!
TLE Step approach:
class Solution {
public int maxValue(int n, int index, int maxSum) {
int maxLeft = index;
int maxRight = n - index - 1;
int sum = n;
int maxIndexValue = 1;
for (int i = 1; sum < maxSum ;i++) {
maxIndexValue++; sum++;
sum += (maxLeft - i > 0 ? i : maxLeft);
sum += (maxRight - i > 0 ? i : maxRight);
}
return maxIndexValue;
}
}
python equivalent O(n)
def maxValue(self, n: int, index: int, maxSum: int) -> int:
value = 1
maxSum -= n # initalize array by 1
left, right = 0, 0
leftMax = index # length of subarray to the left of index
rightMax = n - index - 1
while maxSum > 0 :
value += 1
leftVal = min(left, leftMax) # [1, 2, 2, 1]
rightVal = min(right, rightMax)
left += 1
right += 1
maxSum -= (1 + leftVal + rightVal)
if leftVal == leftMax and rightVal == rightMax:
break
if maxSum > 0:
value += maxSum // n
return value-1 if maxSum < 0 else value