Posts

Showing posts with the label Array

Maximum Sum Circular Subarray

Given a circular array   C of integers represented by  A , find the maximum possible sum of a non-empty subarray of C . Here, a  circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length , and C[i+A.length] = C[i]  when  i >= 0 .) Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j] , there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length .)   Example 1: Input: [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3 Example 2: Input: [5,-3,5] Output: 10 Explanation:   Subarray [5,5] has maximum sum 5 + 5 = 10 Example 3: Input: [3,-1,2,-1] Output: 4 Explanation:   Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4 Example 4: Input: [3,-2,2,-3] Output: 3 Explanation:   Subarray [3] and [3,-2...

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.   Example 2: Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.   class Solution { public boolean canJump(int[] nums) { int i, max = 0, length = nums.length; for(i=0;i<length && i<=max;i++){ if(i+nums[i]>max){ max = i+nums[i]; } } return i == length; } }   Try it on Leetcode  Here, we are going to solve exactly what the question explains. 1) As problem statement indi...

Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i] . Example: Input: [1,2,3,4] Output: [24,12,8,6]     Constraint:  It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer. Note: Please solve it without division . class Solution {     public int[] productExceptSelf(int[] nums) {                 int prod = 1, k=0;         int []res = new int[nums.length];         for(int i=0;i<nums.length;i++){             prod = 1;             for(int j=0;j<nums.length;j++){      ...

Perform String Shifts - Leetcode

You are given a string s  containing lowercase English letters, and a matrix  shift , where  shift[i] = [direction, amount] : direction  can be 0  (for left shift) or 1  (for right shift).  amount  is the amount by which string  s  is to be shifted. A left shift by 1 means remove the first character of s and append it to the end. Similarly, a right shift by 1 means remove the last character of s and add it to the beginning. Return the final string after all operations. Example 1: Input: s = "abc", shift = [[0,1],[1,2]] Output: "cab" Explanation:   [0,1] means shift to left by 1. "abc" -> "bca" [1,2] means shift to right by 2. "bca" -> "cab" Example 2: Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]] Output: "efgabcd" Explanation:   [1,1] means shift to right by 1. "abcdefg" -> "gabcdef" [1,1] means shift to right by 1. "gabcdef" -> ...

Contiguous Array - Leetcode

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0  and 1. Example 2: Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number  of 0 and 1.   Note: The length of the given binary array will not exceed 50,000.     class Solution { public int findMaxLength ( int [] nums) { Map<Integer, Integer> map = new HashMap<>(); map.put( 0 , - 1 ); int ans = 0 ; int balance = 0 ; for ( int i = 0 ; i < nums.length; i++) { balance += nums[i] == 1 ? 1 : - 1 ; if (map.containsKey(balance)) { ans = Math.max(ans, i - map.get(balance)); } else { map.put(balance, i); } } retur...

Maximum Subarray - Leetcode

Given an integer array nums , find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation:  [4,-1,2,1] has the largest sum = 6.   class Solution { public int maxSubArray(int[] nums) { int i, j, max1 = 0, max2 = Integer.MIN_VALUE, sum=0; for(i=0;i<nums.length;i++){ sum = nums[i]; max1 = nums[i]; for(j=i+1;j<nums.length;j++){ sum += nums[j]; if(sum>max2){ max2 = sum; } } if(max1>=max2){ max2 = max1; } } return max2; } }   Here we are taking each element and calculating sum till the end. Storing that max value and again repeating previous steps until end of array. If anyone had different solution leave it as a comment. Try this on Leetcode

Single Number - Leetcode

Given a non-empty  array of integers, every element appears twice except for one. Find that single one. Example 1: Input: [2,2,1] Output: 1   Example 2: Input: [4,1,2,1,2] Output: 4     class Solution { public int singleNumber(int[] nums) { int result = 0 ; for ( int i : nums) { result ^= i; } return result;   } }  Here we are going to do XOR operation. Because each number in array is repeated twice. So, XOR of same number is always 0 and  number which is not repeated will be stored in result.

Counting Elements - Leetcode

Given an integer array arr , count element  x such that x + 1 is also in arr . If there're duplicates in  arr , count them seperately. Example 1: Input: arr = [1,2,3] Output: 2 Explanation:  1 and 2 are counted cause 2 and 3 are in arr.   Example 2: Input: arr = [1,1,3,3,5,5,7,7] Output: 0 Explanation:  No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.   Example 3: Input: arr = [1,3,2,3,5,0] Output: 3 Explanation:  0, 1 and 2 are counted cause 1, 2 and 3 are in arr.   Example 4: Input: arr = [1,1,2,2] Output: 2 Explanation:  Two 1s are counted cause 2 is in arr. Constraints: 1 <= arr.length <= 1000 0 <= arr[i] <= 1000  Here the array to be converted as ArrayList or it can be done within the array itself . But if we done using only array then it consumes more time. Now consider for arraylist solution. 1)Retrieve each element from array using for each loop. 2)For each n ele...

Best Time to Buy and Sell Stock II - Leetcode

Say you have an array for which the i th element is the price of a given stock on day i . Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example 1: Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5),    Then buy on day 4 (price = 3) and sell on day 5 (price = 6),  profit = 6-3 = 3.   Example 2: Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5),  profit = 5-1 = 4.  Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are  engaging multiple transactions at the same time. You must sell before buying again.   Example 3: Input: [7,6,4,3,1] Output: 0 Explanation: In...

Move Zeroes - LeetCode

Given an array nums , write a function to move all 0 's to the end of it while maintaining the relative order of the non-zero elements. Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0]     class Solution { public void moveZeroes(int[] nums) { int i, tmp=0; for(i=0;i<nums.length;i++){ if(nums[i]!=0){ nums[tmp++] = nums[i]; } } for(i=tmp;i<nums.length;i++){ nums[i] = 0; } } }    Click this link to try it on Leetcode     Here, the solution has to be completed in a in-build function.  In this we are going to take a temporary variable starts from 0 and  changing the array by updating the non-zero values to the same array.  Once the traversal is completed, temporary variable describes the  count of zeroes. Then starting from temporary variable position  till end of array has to be updates as 0.  ...