Problem You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Sometimes k is also denoted as w. Example Example ...
Refer the problem statement: Maximum Subarray Sum Let us try to understand how Kadane’s Algorithm work. This solution is similar to sliding window in a way. Pseudocode For at-least 1 non-negative numbers Here’s the pseudocode for Kadane’s algorithm based on your template, designed to handle arrays with non-negative sums: # Start maxGlobal <- 0 maxCurrent <- 0 # Loop over array for i from 0 to n-1 do maxCurrent <- maxCurrent + a[i] # If maxCurrent drops below 0, reset it to 0 if maxCurrent < 0 then maxCurrent <- 0 end if # Update maxGlobal if we've found a new maximum if maxGlobal < maxCurrent then maxGlobal <- maxCurrent end if end for ...
Problem Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead. OR Given an array of positive integers a and a positive number K, find the length of the smallest contiguous subarray whose sum is greater than or equal to K. Return 0 if no such subarray exists. ...
Problem You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. OR ...
Problem There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints. In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards. Your score is the sum of the points of the cards you have taken. Given the integer array cardPoints and the integer k, return the maximum score you can obtain. ...
Problem Given a string, find the length of the longest substring without repeating characters. Examples Example 1: Input: s = "aababcbb" Output: 3 Explanation: The longest substring without repeating characters is "abc". Example 2: Input: s = "cccc" Output: 1 Explanation: The longest substring without repeating characters is "c". ...
Problem The frequency of an element is the number of times it occurs in an array. You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1. Return the maximum possible frequency of an element after performing at most k operations. Examples Example 1: Input: nums = [1,2,4], k = 5 Output: 3 Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4]. 4 has a frequency of 3. ...
Problem Given a string, find the longest substring that contains only k unique or distinct characters. Examples Example 1: Input: S = "aabacbebebe", K = 3 Output: 7 Explanation: "cbebebe" is the longest substring with 3 distinct characters. Example 2: Input: S = "aaaa", K = 2 Output: -1 Explanation: There's no substring with 2 distinct characters. ...
Problem This problem is variant of Minimum Size Subarray Sum Problem Solution Method 1 - Brute Force This is similar to the brute force approach we discussed for the original problem. The only difference is that we’re checking if the subarray sum is equal to K instead of greater than or equal to K. Code Java public class Solution { private static int minSubArrayLenWithSumK(int[] a, int K) { int n = a.length; int ans = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { int currSubarraySum = 0; for(int j = i; j < n; j++) { currSubarraySum += a[j]; if(currSubarraySum == K) { ans = Math.min(ans, j-i+1); break; } if(currSubarraySum > K) { break; } } } return ans == Integer.MAX_VALUE ? 0 : ans; } } ...