Problem Given a list of integers S and a target number k, write a function that returns a true if there is subset of S that adds up to k. If such a subset cannot be made, then return false. Examples Example 1: nums = [2, 3, 5], k = 7 Output: true Explanation: Subset is [2, 5] ...
Problem Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Examples Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. ...
Problem Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library’s sort function. By the way this is Dutch National Flag - 🇳🇱. ...
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 integer write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0. OR Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. ...
Problem Given an array of integer write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k. Example Example 1: Input: nums= [3,1,7,4,5,9,10] , k = 21; Output: [ [7, 4, 10] ] Follow up What if Duplicates Not Allowed? Solution Method 1 - Brute Force Use 3 nested loops and find the 3 elements which sum to k. ...
Problem You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x, y in A with x+y=T. OR Given an array of integers, find two numbers such that they add up to a specific target number. Variant: Return the indices instead of the elements in array. Example Example 1: ...
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 Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Examples Example 1: Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). ...
Problem This problem is similar to 2Sum Problem, only difference is input array is now sorted. Detailed problem Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. ...