gauravkr0071

/*
152. Maximum Product Subarray
Medium


Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

gauravkr0071

/*
1099. Two Sum Less Than K (https://leetcode.com/problems/two-sum-less-than-k/): Given an array A of integers and integer K, 
return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K.
If no i, j exist satisfying this equation, return -1.
1099. Two Sum Less Than K (#1 Sort + Two pointer).java
*/


// Sort + Two pointer solution
// Time: O(nlogn), 1ms

gauravkr0071

//METHOD 1- BRUTE FORCE
//METHOD-2- HASH MAP,
/*
Given an array arr of N elements, the task 
is to find the length of the smallest subarray of
the given array that contains at least one duplicate
element. A subarray is formed from consecutive elements of
an array. If no such array exists, print “-1”.
link- https://www.geeksforgeeks.org/find-the-smallest-subarray-having-atleast-one-duplicate/ 

gauravkr0071

#include<iostream>
#include<climits>
using namespace std;
 
int maxSubArraySum(int a[], int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0;
 
    for (int i = 0; i < size; i++)
    {

gauravkr0071

int lengthOfLongestSubstring(string s) {
        vector<int> map(128,0);
        int counter=0, begin=0, end=0, d=0; 
        while(end<s.size()){
            if(map[s[end++]]++>0) counter++; 
            while(counter>0) if(map[s[begin++]]-->1) counter--;
            d=max(d, end-begin); //while valid, update d
        }
        return d;
    }

gauravkr0071

int lengthOfLongestSubstringTwoDistinct(string s) {
        vector<int> map(128, 0);
        int counter=0, begin=0, end=0, d=0; 
        while(end<s.size()){
            if(map[s[end++]]++==0) counter++;
            while(counter>2) if(map[s[begin++]]--==1) counter--;
            d=max(d, end-begin);
        }
        return d;
    }

gauravkr0071

*/
  
   Minimum Window Substring
Hard

7469

471

Add to List

gauravkr0071

/*
Given an array of __POSITIVE INTEGERS__ nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 DO NOT work if elements are negative

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

gauravkr0071

/*
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

 k can also be zero

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Example 2:

gauravkr0071

/*
find the longest subbary with sum k,
k can also be zero, return -1 if no array with sum k is present
*/
  unordered_map<int, int>u;
  int len=INT_MIN;
 for(int i=0;i<nums.size();i++)
      {
          temp+=nums[i];