Largest sum contiguous sub-array
class Solution{ // arr: input array // n: size of array //Function to find the sum of contiguous subarray with maximum sum. long maxSubarraySum(int arr[], int n){ // Your code here //we will use kadane's algorithms for solving this problem long max = Integer.MIN_VALUE; long currentMax = 0; for(int i =0;i<arr.length;i++){ currentMax+=arr[i]; if(currentMax>max) max = currentMax; if(currentMax<0) currentMax=0; } return max; } } Search in a row-wise and column wise sorted matrix
class Sol { public static int matSearch(int mat[][], int N, int M, int X) { for(int i =0;i<mat.length;i++){ if(binarySearch(mat[i],0,mat[i].length-1,X) ==1) return 1; } return 0; } public static int binarySearch(int arr[], int start, int end, int target){ if(start<=end){ int mid = start + (end-start)/2; if(arr[mid] == target) return 1; if(arr[mid] < target) return binarySearch(arr, mid+1, end, target); else return binarySearch(arr,start,mid-1, target); } return 0; } } Brute force Approach(This will lead to TLE)
class Solution { //Function to rotate an array by d elements in counter-clockwise direction. static void rotateArr(int arr[], int d, int n) { for(int i =0;i<d;i++){ rotate(arr); } } public static void rotate(int arr[]){ int i =0; int temp = arr[i]; while(i<arr.length-1){ arr[i] = arr[i+1]; i++; } arr[arr.length-1] = temp; } } Optimized Approach
TC : O(n) , space complexity : O(N) for using extra space for result array
class Solution { //Function to rotate an array by d elements in counter-clockwise direction. static void rotateArr(int arr[], int d, int n) { int i = 0,j =d % n; int result[] = new int[n]; while(j<n){ result[i++] = arr[j++]; } int index= 0; while(index<d && i < n){ result[i++] = arr[index++]; } for(int k =0;k<n;k++) arr[k] = result[k]; } } Print given matrix in a spiral form
Time complexity : O(MxN) for traversing the matrix, space complexity: O(MxN) for using ArrayList which will be of size MxN
class Solution { //Function to return a list of integers denoting spiral traversal of matrix. static ArrayList<Integer> spirallyTraverse(int matrix[][], int r, int c) { // code here //top down right bottom ArrayList<Integer> list = new ArrayList<>(); int topLeft = 0, topRight= c-1, bottomLeft = 0, bottomRight =r-1; int chance = 0;//1,2,3 while(topLeft<=bottomRight && bottomLeft <=topRight){ if(chance ==0){ //move left to right for(int i = bottomLeft;i<=topRight;i++){ list.add(matrix[topLeft][i]); } topLeft++; chance =1; } else if(chance ==1){ //move form top to bottom for(int i = topLeft;i<=bottomRight;i++){ list.add(matrix[i][topRight]); } topRight--; chance = 2; } else if(chance ==2){ //move right to left for(int i = topRight;i>=bottomLeft;i--){ list.add(matrix[bottomRight][i]); } bottomRight--; chance = 3; } else { //move from bottom to top for(int i = bottomRight;i>=topLeft;i--){ list.add(matrix[i][bottomLeft]); } bottomLeft++; chance = 0; } } return list; } } Solution 1: We can use o(n^2) solution , using two for loops to find pairs that will add up to target.
Solution 2: We can also use backtracking to find all the possible pairs whose sum is target (time complexity will be (2^n) as every index will have two choices take or not take
class Solution { int getPairsCount(int[] arr, int n, int k) { //ArrayList<Integer> list = new ArrayList<>(); //return pairs(0,arr,k,list); Arrays.sort(arr); int i =0, j = n-1; while(i<j){ if(arr[i]+arr[j] ==k) { } } } public int pairs(int index,int[] arr, int target,ArrayList<Integer> list){ //base case if(index >= arr.length){ if(target==0){ //System.out.println("here" +list.size()); return list.size() ==2 ? 1 : 0; } return 0; } if(target==0){ //System.out.println("here" + list.size()); return list.size() ==2 ? 1 : 0; } //lets take it int left =0; if(target>=arr[index]){ list.add(arr[index]); left = pairs(index+1,arr,target-arr[index],list); //don't take , I am adding it here because of the if condition we have used list.remove(list.size()-1); } int right = pairs(index+1,arr,target,list); return left + right; } } But both of these solution will lead to TLE
Optimal Solution :
Using HashMap
TC: O(n)
class Solution { int getPairsCount(int[] arr, int n, int k) { // we will use simple hashing technique, // first we will find the frequency of all the elements int the array. Map<Integer,Integer> map = new HashMap<>(); for(int i : arr) map.put(i,map.getOrDefault(i,0)+1); //we will increment count value based on value of (k-arr[i]) as key in the //map //for example we have k =6, arr=1,5,0, // there is only one pair 1,5 that form 6 //map = 1=1,5=1,0=1 // so, map.get(6-1) = map.get(5) = 1 //map.get(6-5) = map.get(1) = 1; //map.get(6-0) = map.get(6) = 0; //total = 1+1+0 = 2; //hence result will be 2/2 = 1 (we divided the result by 2 because it contains duplicate // as (1,5) and (5,1) hence only one uniqueue pair is taken into consideration) int count =0; for(int i =0;i<n;i++){ count = count + map.getOrDefault(k-arr[i],0); //we have to avoid pair of the same index element like( arr[i],arr[i]) if(k == arr[i]+arr[i]) count--; } return count/2; } } TC : O(n) and space complexity = O(2n)~O(n) for using leftMaxima and rightMaxima arrays
class Solution{ // arr: input array // n: size of array // Function to find the trapped water between the blocks. static long trappingWater(int arr[], int n) { // Your code here int[] leftMaxima = new int[n]; int[] rightMaxima = new int[n]; int currentMaxima = Integer.MIN_VALUE; for(int i =0;i<n;i++){ if(currentMaxima < arr[i]) { currentMaxima = arr[i]; leftMaxima[i] = arr[i]; } else leftMaxima[i] = currentMaxima; } currentMaxima = Integer.MIN_VALUE; for(int i = n-1;i>=0;i--){ if(currentMaxima < arr[i]){ currentMaxima = arr[i]; rightMaxima[i] = arr[i]; } else rightMaxima[i] = currentMaxima; } int loggedWater = 0; for(int i =0;i<n;i++){ loggedWater+=Integer.min(leftMaxima[i],rightMaxima[i])-arr[i]; } return loggedWater; } } Remove duplicate from the sorted array
//TC: o(N) + o(N) for two passes,space complexity : o(N) for using list //not optimal class Solution { public int removeDuplicates(int[] nums) { List<Integer> list = new ArrayList<>(); int count = 0; for(int i : nums) if(!list.contains(i)) list.add(i); int index = 0; for(Integer val: list){ nums[index] = val; index++; } return list.size(); } } //TC: o(N) , space complexity: O(1) //optimized class Solution { public int removeDuplicates(int[] nums){ int i =0,j = i+1; while(j<nums.length){ if(nums[i] == nums[j]){ j++; continue; } if(nums[i] !=nums[j]){ int temp = nums[j]; nums[i+1] = nums[j]; nums[j] = temp; i++; } } return i+1; } } Maximum product in contiguous subarray
TC:O(n),SC:constant
Inspired from Kadane's algorithm
import java.util.ArrayList; public class Solution { public static int maximumProduct(ArrayList<Integer> list, int n) { int a,b,c; a=b=c= list.get(0); for(int i =1;i<list.size();i++){ int currentVal = list.get(i); int temp = Integer.max(currentVal, Integer.max(a*currentVal,b*currentVal)); b = Integer.min(currentVal, Integer.min(a*currentVal,b*currentVal)); a = temp; c = Integer.max(a,c); } return c; } } Generate Pascal's triangle
TC: O(NM) where N is the no. of rows and M is max of elements in the row
class Solution { public List<List<Integer>> generate(int numRows) { // we will use simple approach List<List<Integer>> list = new ArrayList<>(); for(int i =1;i<=numRows;i++){ // to keep track of row of the pyramid List<Integer> l = new ArrayList<>(); int size = i; for(int j =0;j<size;j++){ if(j==0) l.add(1); // it its the first index it will have 1 else{// for any index between first and last //get the last row list List<Integer> temp = list.get(list.size()-1); while(j<size-1){ // we will run while loop before last index l.add(temp.get(j) + temp.get(j-1)); // think about it what it does, /* it the repvious row had 1 2 2 1 next row will have 1 3 3 3 1 this is what line 15 calculates */ j++; } l.add(1); // it is last index it will have value 1 } } list.add(l); System.out.println(list + " size "+ size); } return list; } } Sort 0,1 and 2
Approach 1 : TC : O(NlogN)
class Solution { public void sortColors(int[] nums) { //way one we can use hashmap for solving this Map<Integer,Integer> map = new TreeMap<>(); for(int i =0;i<nums.length;i++) map.put(nums[i],map.getOrDefault(nums[i],0)+1); int index = 0; for(Map.Entry<Integer,Integer> entry: map.entrySet()){ for(int i =0;i<entry.getValue();i++){ nums[index++] = entry.getKey(); } } } } Approach 2 : TC : O(n)
Strivers sde sheet solution
Optimal solution : TC: O(NlogN) + O(N) , nlogn for sorting and n for iterating
class Solution { public int[][] merge(int[][] intervals) { if(intervals.length ==0 || intervals ==null) return new int[0][]; Arrays.sort(intervals,(a,b)->a[0]-b[0]); // this is great snippet for sorting List<int[]> list = new ArrayList<>(); int start = intervals[0][0]; int end = intervals[0][1]; for(int i[] : intervals){ if(end >= i[0]){ end = Integer.max(end,i[1]); } else{ list.add(new int[]{start,end}); start = i[0]; end = i[1]; } } list.add(new int[]{start,end}); return list.toArray(new int[0][]); } } Finding missing and repeating number
import java.util.*; //Solution 1 : using circular sorting (Leads to TLE) // public class Solution { // public static int[] missingAndRepeating(ArrayList<Integer> arr, int n) { // // Write your code here // //we can use circular sorting for this // //remember circular sorting is only applicable , if the if the values in the array are in the range of length of the array. // int i =0; // while(i<n){ // int j = arr.get(i)-1; // if(arr.get(j)!=arr.get(i)){ // swap(arr,i,j); // } // else i++; // } // int result[] = new int[2]; // for(int k =0;k<n;k++){ // if(arr.get(k)!=k+1){ // result[0] = k+1; // result[1] = arr.get(k); // break; // } // } // return result; // } // public static void swap(ArrayList<Integer> arr,int i,int j){ // int temp = arr.get(i); // arr.set(i,arr.get(j)); // arr.set(j,temp); // } // } //Solution 2 : using HashMap TC: O(n) public class Solution{ public static int[] missingAndRepeating(ArrayList<Integer> arr,int n){ HashMap<Integer,Integer> map = new HashMap<>(); int result[]= new int[2]; Arrays.fill(result,-1); for(Integer i : arr) map.put(i,map.getOrDefault(i,0)+1); //stem.out.print(map); for(int i =0;i<n;i++){ if(map.containsKey(i+1)){ if(map.get(i+1) > 1) result[1] = (i+1); } else result[0] = i+1; if(result[0]!=-1 && result[1]!=-1) break; } return result; } } TC:O(logn)
//this is naive approach its not optimal its gonna take O(N) time // class Solution { // public double myPow(double x, int n) { // double result = 1.0; // for(int i =0;i<Math.abs(n);i++){ // result = result*x; // } // if(n<0) return 1/result; // return result; // } // } //we will use something called binary exponential approach //this uses the concept of odd and even exponential //if x^n if n is even it can be written as (x^2)^(n/2) //if x^n is odd then it can be written as x* (x^(n-1)) here (x^(n-1)) is again even so same approach //solution: class Solution{ public double myPow(double x, int n){ double result =1.0; long nn =n; if(n<0) nn = -1*nn; while(nn > 0){ if(nn%2==0){ x = x*x; nn = nn/2; } else{ result = result*x; nn = nn-1; } } if(n<0) result = (double)( 1.0)/(double)(result); return result; } } TC: O(NLogN) as we are using merge sort as optimal solution, brute force will take O(N^2)
import java.util.* ; import java.io.*; /* // Approach 1: brute force approach public class Solution { public static long getInversions(long arr[], int n) { // Write your code here. long result = 0; for(int i =0;i<arr.length;i++){ for(int j =i+1;j<arr.length;j++){ if(arr[i] > arr[j]) result++; } } return result; } } */ //using merge sort time complexity is : O(nlogn) public class Solution{ public static long getInversions(long arr[],int n){ return merge(0,n-1,arr); } public static long merge(int start, int end, long[] arr){ long count = 0; if(end > start){ int mid = start + (end-start)/2; count+=merge(start,mid,arr); count+=merge(mid+1,end,arr); count+=sort(start,mid,end,arr); } return count; } public static long sort(int s,int m,int e, long[] arr){ long[] p = new long[m-s+1]; long[] q = new long[e-m]; for(int i =0;i<p.length;i++) p[i] = arr[i+s]; for(int i =0;i<q.length;i++) q[i] = arr[i+m+1]; int i=0,j=0,k=s; long count = 0; while(i<p.length && j < q.length){ if(p[i]<=q[j]){ arr[k] = p[i]; k++;i++; } else{ arr[k] = q[j]; count+=p.length-i; // just think about it //if p[i] > q[j] then all the elements after ith index in p array //will also be greater than q[j] because p and q are sorted //hence total pairs = totalNoOfElements between ith index and last index including ith and last element as well = p.length-i; k++;j++; } } while(i<p.length){ arr[k] = p[i]; i++;k++; } while(j<q.length){ arr[k]=q[j]; j++;k++; } return count; } } TC:O(nlogn)
class Solution { public int reversePairs(int[] nums) { return merge(0,nums.length-1,nums); } public int merge(int start, int end, int[] arr){ int count = 0; if(end > start){ int mid = start + (end-start)/2; count+=merge(start,mid,arr); count+=merge(mid+1,end,arr); count+=sort(start,mid,end,arr); } return count; } public int sort(int s,int m,int e, int[] arr){ int[] p = new int[m-s+1]; int[] q = new int[e-m]; int count =0; int t = m+1; for(int u =s;u<=m;u++){ while(t<=e && arr[u] > (long) 2*arr[t]){ t++; } count+=t-(m +1); } for(int i =0;i<p.length;i++) p[i] = arr[i+s]; for(int i =0;i<q.length;i++) q[i] = arr[i+m+1]; int i=0,j=0,k=s; while(i<p.length && j < q.length){ if(p[i]<=q[j]){ arr[k] = p[i]; k++;i++; } else{ arr[k] = q[j]; k++;j++; } } while(i<p.length){ arr[k] = p[i]; i++;k++; } while(j<q.length){ arr[k]=q[j]; j++;k++; } return count; } } Maximum Index
TC:O(nlogn),SC: O(n)
I was asked this question in ServiceNow Interview
PS: I was not able to give optimized solution( status : rejected)
class Solution{ // A[]: input array // N: size of array // Function to find the maximum index difference. static int maxIndexDiff(int A[], int N) { //lets assume A[] = {34, 8, 10, 3, 2, 80, 30, 33, 1} // Your code here int rightMaxima[] = new int[A.length]; int currentMax = Integer.MIN_VALUE; for(int i =A.length-1;i>=0;i--){ currentMax = Integer.max(currentMax,A[i]); rightMaxima[i] = currentMax; } //now rightMaxima = {80,80,80,80,80,80,33,33,1} //we will use binary search on rightMaxima for each element to find rightmost //value that is greater than current element and we will store the index difference //and finally we will return the maximum index difference int result =0; for(int i =0;i<N;i++){ int ans = i;// intially we assume that current index is the index that satisfies the condition (which is true unless we find other index) int low = i+1, high = N-1;// for every index i , we will have to search in i+1 to N-1 array range to //find the rightmost element in the rightMaxima array that satisfies the condition of // A[i]<=A[j] while(low<=high){ int mid = (low + high)/2; if(A[i]<=rightMaxima[mid]){ //it means that either mid or between mid+1, N-1, we have right most element that satisfies the condition ans = Integer.max(ans,mid); low = mid+1; } else high = mid-1; } result = Integer.max(result,ans-i);// so basically we are finding max index difference for all the indexes // we will return the max one only } return result; } } 
Top comments (0)