Posts

Longest Subarray with Sum greater than Equal to K

-
Given an array of N integers. The task is to find the maximum length subarray such that the sum of all its elements is greater than or equal to K. Input: arr[]= {-1, 4, -2, -5, 6, -8}, K=0 Output: 5 Explanation: {-1, 4, -2, -5, 6} forms the longest sub array  with sum=2. Discussion : class Pair { private int sum ; private int index ; Pair ( int sum , int index ){ this . index = index ; this . sum = sum ; } public int getSum () { return sum ; } public int getIndex () { return index ; } } import java.util.* ; public class test { static int findInd ( ArrayList < Pair > preSum , int n , int val ) { int l = 0 , h = n - 1 , mid ; int ans = - 1 ; while ( l <= h ) { mid = l + ( h - l )/ 2 ; if ( preSum . get ( mid ). getSum () <= val ) { ans = mid ; ...
Post a Comment
Read more

Shortest Subarray with Sum at Least K

-
Problem Link Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K. If there is no non-empty subarray with sum at least K, return -1. Discussion : public int shortestSubarray ( int [] A , int K ) { int N = A . length , res = N + 1 ; int [] B = new int [ N + 1 ]; for ( int i = 0 ; i < N ; i ++) B [ i + 1 ] = B [ i ] + A [ i ]; Deque < Integer > d = new ArrayDeque <>(); for ( int i = 0 ; i < N + 1 ; i ++) { while ( d . size () > 0 && B [ i ] - B [ d . peekFirst ()] >= K ) res = Math . min ( res , i - d . pollFirst ()); while ( d . size () > 0 && B [ i ] <= B [ d . peekLast ()]) d . pollLast (); d . addLast ( i ); } return res <= N ? res : - 1 ; }
Post a Comment
Read more

Minimum Size Subarray Sum

-
Given an array of  n  positive integers and a positive integer  s , find the minimal length of a  contiguous  subarray of which the sum ≥  s . If there isn't one, return 0 instead. Discussion : public int minSubArrayLen ( int s , int [] nums ) { int n = nums . length ; int ans = Integer . MAX_VALUE ; int left = 0 ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++) { sum += nums [ i ]; while ( sum >= s ) { ans = Math . min ( ans , i + 1 - left ); sum -= nums [ left ++]; } } return ( ans != Integer . MAX_VALUE ) ? ans : 0 ; }
Post a Comment
Read more

Maximum Size Subarray Sum Equals k

-
Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead. Discussion : public int maxSubArrayLen ( int [] nums , int k ) { HashMap < Integer , Integer > map = new HashMap <>(); map . put ( 0 , - 1 ); int result = 0 ; int sum = 0 ; for ( int i = 0 ; i < nums . length ; i ++){ sum += nums [ i ]; if ( map . containsKey ( sum - k )){ result = Math . max ( result , i - map . get ( sum - k )); } map . putIfAbsent ( sum , i ); } return result ; }
Post a Comment
Read more

Buy and Sell Stock with at most k transactions

-
In share trading, a buyer buys shares and sells on a future date.  Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. A  new transaction can only start after the previous transaction is complete. Discussion : public int maxProfit ( int k , int [] prices ) { int len = prices . length ; if ( len == 0 ) return 0 ; int profit [][] = new int [ k + 1 ][ len ]; for ( int i = 1 ; i < k + 1 ; i ++){ int maxthusfar = Integer . MIN_VALUE ; for ( int j = 1 ; j < len ; j ++){ maxthusfar = Math . max ( maxthusfar , profit [ i - 1 ][ j - 1 ]- prices [ j - 1 ]); profit [ i ][ j ] = Math . max ( profit [ i ][ j - 1 ], maxthusfar + prices [ j ]); } } return profit [ k ][ len - 1 ]; }
Post a Comment
Read more

Word Break Problem

-
Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. Consider the following dictionary  { i, like, sam, sung, samsung, mobile, ice,  cream, icecream, man, go, mango} Input:  ilike Output: Yes  The string can be segmented as "i like". Discussion : public boolean wordBreak ( String s , List < String > wordDict ) { if ( s == null || s . length () == 0 ) return false ; int n = s . length (); boolean [] dp = new boolean [ n ]; for ( int i = 0 ; i < n ; i ++) { for ( int j = 0 ; j <= i ; j ++) { String sub = s . substring ( j , i + 1 ); if ( wordDict . contains ( sub ) && ( j == 0 || dp [ j - 1 ])) { dp [ i ] = true ; break ; } } } return dp [ n - 1 ]; }
Post a Comment
Read more

Graph is Bipartite or not?

-
A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set. A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. Note that it is possible to color a cycle graph with even cycle using two colors. We can solve this problem using  Breadth First Search (BFS). Discussion : public static boolean isBipartiteUtil ( int G [][], int src , int colorArr []) { colorArr [ src ] = 1 ; LinkedList < Integer > q = new LinkedList < Integer >(); q . add ( src ); while (! q . isEmpty ()) { int u = q . poll (); if ( G [ u ][ u ] == 1 ) return false ; ...
Post a Comment
Read more