Posts

Showing posts with the label #leetcode

Partition Equal Subset Sum

Partition Equal Subset Sum: Problem Description: Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Example 1: Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. Example 2: Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.   Constraints: 1 <= nums.length <= 200 1 <= nums[i] <= 100 Solution: class Solution {     public boolean canPartition(int[] nums) {         int totalsum = 0, subsetsum = 0;         for(int num: nums)             totalsum+=num;         if(totalsum%2 == 0)             subsetsum = totalsum/2;         else return false;         int n = nums.length;   ...
Post a Comment
Read more

Sum of All Odd Length Subarrays

Image
Sum of All Odd Length Subarrays: Problem Description: Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays. A subarray is a contiguous subsequence of the array. Return the sum of all odd-length subarrays of arr. Example 1: Input: arr = [1,4,2,5,3] Output: 58 Explanation: The odd-length subarrays of arr and their sums are: [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1,4,2] = 7 [4,2,5] = 11 [2,5,3] = 10 [1,4,2,5,3] = 15 If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58 Example 2: Input: arr = [1,2] Output: 3 Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3. Example 3: Input: arr = [10,11,12] Output: 66   Constraints: 1 <= arr.length <= 100 1 <= arr[i] <= 1000 Solution: Optimized Solution: class Solution {     public int sumOddLengthSubarrays(int[] arr) {         int n = arr.length, res = 0, start = 0, end = 0,elementappearsinhowmanysubarrays ...
Post a Comment
Read more

Running Sum of 1d Array

Image
Running Sum of 1d Array: Problem Description: Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of nums. Example 1: Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. Example 2: Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]. Example 3: Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17]   Constraints: 1 <= nums.length <= 1000 -10^6 <= nums[i] <= 10^6 Solution: class Solution {     public int[] runningSum(int[] nums) {         int sm = 0;         int[] runningSum = new int[nums.length];         for(int i=0; i < nums.length; i++){             sm += nums[i];             runningSum[i] = sm;         }   ...
Post a Comment
Read more

Maximum Subarray

Image
Maximum Subarray  Problem Problem Description: Given a sequence of n real numbers A(1) … A(n), determine a contiguous subsequence A(i) … A(j) for which the sum of elements in the subsequence is maximized. Problem Solution: We will proceed in a linear fashion maintaining overall_max and current_max variables. If adding the current element to current_max results in overall maximum value, we will replace the value of overall_max variable. Otherwise, we will proceed furthere. Expected Input and Output: Case-1: A[]={2,4,6,8} maximum contiguous subarry= {2, 4, 6, 8} maximum contiguous subarray sum= 20 Case-2: A[]={-2, 3, -7, 5, -9} maximum contiguous subarry= {5} maximum contiguous subarray sum= 5 Case-3: A[]={3, -4, 7, -9, 8, 7} maximum contiguous subarry= {8, 7} maximum contiguous subarray sum= 15   A[]={3, -4, 9, -8, 8, 7} maximum contiguous subarry= {9, -8, 8, 7} maximum contiguous subarray sum= 16 Case-4: A[]={3, -4, 9, -8, 8, 7} maximum contiguous subarry= {9, -8, 8, 7} maximu...
Post a Comment
Read more

Two Sum II - Input array is sorted

Image
Two Sum II - Input array is sorted: Problem Description: Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note: Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.   Example 1: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. Example 2: Input: numbers = [2,3,4], target = 6 Output: [1,3] Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2]   Constraints: 2 <= nums.length <= 3 * 104 -1000 <= nums[i] <= 1000 nums is sorted in increasing order. -1000 <= target <= 1000 Program: class Solution {     public int[] twoSum(int[] num...
Post a Comment
Read more

Shuffle the Array

Program Description: Shuffle the Array Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn]. Return the array in the form [x1,y1,x2,y2,...,xn,yn]. Example 1: Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7]  Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7]. Example 2: Input: nums = [1,2,3,4,4,3,2,1], n = 4 Output: [1,4,2,3,3,2,4,1] Example 3: Input: nums = [1,1,2,2], n = 2 Output: [1,2,1,2] Constraints: 1 <= n <= 500 nums.length == 2n 1 <= nums[i] <= 10^3 Solution : class Solution {     public int[] shuffle(int[] nums, int n) {         int InsertValue = nums[n];         for(int i=1; i< nums.length; i+=2){             if(n>nums.length-1){                 break;             }             InsertValue = nums[n]; ...
Post a Comment
Read more

Running Sum of 1D Array

Program Description: Running Sum of 1D Array Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of nums. Example 1: Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. Example 2: Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]. Example 3: Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17]   Constraints: 1 <= nums.length <= 1000 -10^6 <= nums[i] <= 10^6 Solution: class Solution {     public int[] runningSum(int[] nums) {         int sm = 0;         int[] runningSum = new int[nums.length];         for(int i=0; i < nums.length; i++){             sm += nums[i];             runningSum[i] = sm;         }   ...
Post a Comment
Read more

Two Sum

Two Sum: Program Description: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1]   Constraints: 2 <= nums.length <= 105 -109 <= nums[i] <= 109 -109 <= target <= 109 Only one valid answer exists. : Solution : class Solution {     public int[] twoSum(int[] nums, int tar) {         Map<Integer, Integer> dic = new HashMap<Integer, Integer>();                  for(int i=0; i<nums.length ; i++){           ...
Post a Comment
Read more