🌱 Keegan's Digital Garden

2555. Maximize Win From Two Segments

2 min read

Leetcode

📝 Problem Details

💭What Were My Initial Thoughts?

- use an unordered map to store the frequencis of numbers 
- iterate through the map to try and find the complement of k and num
- if an element exists then we assume that a "prize" can be won
- push it into a prizes vector
- return the last 2 elements in the vector

🤔What Did I Struggle With?

- my above thoughts were incorrect
- iteration through the list to calculate prizes
- dealing with maximizng prizes with overlapping integers
- memorization and DP implementation

💡 Explanation of Solution

1. Sliding Window: use left and right pointers to maintain the range of positions within k. Adjust left while the range exceeds k

3. Count Prizes: use the diff between left and right to calculate the number of prizes in our window

4. Dynamic Programming: 
	- use a dp array to store the maximum number of prizes you can win up to a certain index
	- combine the current window's prizes with the maximum from a previous non-overlapping range

⌛ Complexity Analysis

Time Complexity: O(n)
- the use of sliding window enables a linear pass through of all elements 
- updating the dp array is done in constant O(1) time for each iteration, so the cost is O(n)

Space Complexity: O(n)
- the use of our dp array takes up O(n) space

💻 Implementation of Solution

class Solution {
public:
	int maximizeWin(vector<int>& prizePositions, int k) {
		int n = prizePositions.size();
		int maxPrizes = 0;
		int left = 0;
 
		vector<int> dp(n + 1, 0); // store the max prizes up to index i
 
		// sliding window to find maximum prizes in range 
		for(int right = 0; right < n; right ++) {
			// shrink the window if it exceeds size k
			while(prizePositions[right] - prizePositions[left] > k) left++;
 
			// calculate the number of prizes in the current node
			int prizesInWindow = right - left + 1;
 
			// update maxPrizes with best combination
			maxPrizes = max(maxPrizes, prizesInWindow + dp[left]);
 
			// store the maximum prizes up to the current index
			dp[right + 1] = max(dp[right], prizesInWindow);
		}
		return maxPrizes;
	}
};

Graph View