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;
}
}
Latest comments (0)