Array program in java | Top 10 Array Coding Problems for Interviews

1.Maximum Index :-

Given an array A[] of N positive integers. The task is to find the maximum of j - i subjected to the constraint of A[i] < A[j] and i < j.

Example 1:

Input:

N = 2

A[] = {1, 10}

Output:

Explanation:

A[0]<A[1] so (j-i) is 1-0 = 1.

Example 2:

Input:

N = 9

A[] = {34, 8, 10, 3, 2, 80, 30, 33, 1}

Output:

Explanation:

In the given array A[1] < A[7]

satisfying the required

condition(A[i] < A[j]) thus giving

the maximum difference of j - i

which is 6(7-1)

C++ code

int maxIndexDiff(int A[], int N)

   {

       // Your code here

       int j=N-1, ans=0;

       for (int i=0;i<N;i++){

                 while (A[i]>A[j] && j>i)

                 j--;

                 ans =max(ans, j-i);

                 j=N-1;

       }

       return ans;

   }

C++ code

int maxIndexDiff(int A[], int N)

   {

       // Your code here

       int j=N-1, ans=0;

       for (int i=0;i<N;i++){

                 while (A[i]>A[j] && j>i)

                 j--;

                 ans =max(ans, j-i);

                 j=N-1;

       }

       return ans;

   }

int maxIndexDiff(int a[], int n)

   {

       int low=0,high=n-1,total=0,diff;

       while(high>=low)

       {

           if(a[high]>=a[low])

           {

               diff=high-low;

               total=max(total,diff);

               low++;

               high=n-1;

           }

           else

           high--;

       }

       return total;

int maxIndexDiff(int a[], int n)

   {

       int low=0,high=n-1,total=0,diff;

       while(high>=low)

       {

           if(a[high]>=a[low])

           {

               diff=high-low;

               total=max(total,diff);

               low++;

               high=n-1;

           }

           else

           high--;

       }

       return total;

   }

2.Max sum path in two arrays

Given two sorted arrays A and B of size M and N respectively. Each array contains only distinct elements but may have some elements in common with the other array. Find the maximum sum of a path from the beginning of any array to the end of any of the two arrays. We can switch from one array to another array only at the common elements.

Note: Only one repeated value is considered in the valid path sum;

Example 1:

Input:

M = 5, N = 4

A[] = {2,3,7,10,12}

B[] = {1,5,7,8}

Output: 35

Explanation: The path will be 1+5+7+10+12

= 35.

Example 2:

Input:

M = 3, N = 3

A[] = {1,2,3}

B[] = {3,4,5}

Output: 15

Explanation: The path will be 1+2+3+4+5=15..

Expected Time Complexity: O(M + N)

Expected Auxiliary Space: O(1)

Constraints:

1 <= M,N <= 104

1 <= A[i], B[i] <= 104

The main idea is to calculate the sum for each array until we come across common element.

sum1 → sum for 1st array

sum2 → sum for 2nd array

maxsum → max sum path

Now when we come across a common element,

add max(sum1,sum2) to maxsum. At this point we have a choice to shift the array. Shifting will be only beneficial if it gives max sum.

Consider the rest of the elements of both array as new problem statement.

Again calculate sum1 and sum2 for both arrays until a common element is found or we reach the end of one of these array.

After calculating sum1 and sum2 check the max of them and we will know weather shifting to next array was benificial or not.

Do the same until we traverse both the array.

int max_path_sum(int A[], int B[], int l1, int l2)

{

int sum1=0,sum2=0,maxsum=0;

int i=0,j=0;

while(i < l1 && j < l2)

{

if(A[i] < B[j])

{

                sum1+=A[i];

                i++;

            }

            else if(B[j] < A[i])

            {

                sum2+=B[j];

                j++;

            }

            else

            {

                maxsum+=max(sum1,sum2)+A[i];

                sum1=0,sum2=0;

                i++;j++;

            }

       }

        while(i < l1)

         sum1+=A[i++];

        while(j < l2)

         sum2+=B[j++];

        return maxsum + max(sum1,sum2);

    }

3.Find Missing And Repeating

Given an unsorted array Arr of size N of positive integers. One number 'A' from set {1, 2, …N} is missing and one number 'B' occurs twice in array. Find these two numbers.

Example 1:

Input:

N = 2

Arr[] = {2, 2}

Output: 2 1

Explanation: Repeating number is 2 and

smallest positive missing number is 1.

Example 2:

Input:

N = 3

Arr[] = {1, 3, 3}

Output: 3 2

Explanation: Repeating number is 3 and

smallest positive missing number is 2.

int *findTwoElement(int *arr, int n) {

       int rep;

       int *ans=new int[2];

       for(int i=0;i<n;i++)

       {

           if(arr[abs(arr[i])-1]>0){

               arr[abs(arr[i])-1]*=-1;

           }

           else{

               rep=abs(arr[i]);

               // cout<<i<<'\n';

           }

       }

       // cout<<rep<<'\n';

       int i=1;

       for( i=1;i<=n;i++){

           // cout<<arr[i-1]<<" ";

           if(arr[i-1]>0)break;

       }

       // cout<<"\n";

       ans[0]=rep;

       ans[1]=i;

       return ans;

       // code here

   }

4.Stock buy and sell

The cost of stock on each day is given in an array A[] of size N. Find all the days on which you buy and sell the stock so that in between those days your profit is maximum.

Note: There may be multiple possible solutions. Return any one of them. Any correct solution will result in an output of 1, whereas wrong solutions will result in an output of 0.

Example 1:

Input:

N = 7

A[] = {100,180,260,310,40,535,695}

Output:

Explanation:

One possible solution is (0 3) (4 6)

We can buy stock on day 0,

and sell it on 3rd day, which will

give us maximum profit. Now, we buy

stock on day 4 and sell it on day 6.

Example 2:

Input:

N = 5

A[] = {4,2,2,2,4}

Output:

Explanation:

There are multiple possible solutions.

one of them is (3 4)

We can buy stock on day 3,

and sell it on 4th day, which will

give us maximum profit.

vector<vector<int> > stockBuySell(vector<int> a, int n){

       vector<vector<int>> v;

       int i=0,buy=0,sell=0;

       for(int i=1;i<n;i++)

       {

           if(a[i]>a[i-1])

           {

               buy=i-1;

               sell=i;

               v.push_back({buy,sell});

           }

       }

          return v;

   }

5.Sum Pair closest to X

Given a sorted array arr[] of size N and a number X, find a pair in array whose sum is closest to X.

Example 1:

Input:

N = 6, X = 54

arr[] = {10, 22, 28, 29, 30, 40}

Output: 22 30

Explanation: As 22 + 30 = 52 is closest to 54.

Example 2:

Input:

N = 5, X = 10

arr[] = {1, 2, 3, 4, 5}

Output: 4 5

Explanation: As 4 + 5 = 9 is closest to 10.

vector<int> sumClosest(vector<int>arr, int x)

   {

       int n = arr.size();

int diff = INT_MAX;

int low = 0, high = n - 1;

int first = 0, second = 0;

while (low < high)

{

if (abs(arr[high] + arr[low] - x) < diff)

{

diff = abs( arr[high] + arr[low] - x );

first = arr[low];

second = arr[high];

}

if (arr[low] + arr[high] > x)

{

high--;

}

else

{

low++;

}

}

vector<int> v;

v.push_back(first);

v.push_back(second);

return v;

   }

};

6.Chocolate Distribution Problem

Given an array A[ ] of positive integers of size N, where each value represents the number of chocolates in a packet. Each packet can have a variable number of chocolates. There are M students, the task is to distribute chocolate packets among M students such that :

1. Each student gets exactly one packet.

2. The difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student is minimum.

Example 1:

Input:

N = 8, M = 5

A = {3, 4, 1, 9, 56, 7, 9, 12}

Output: 6

Explanation: The minimum difference between

maximum chocolates and minimum chocolates

is 9 - 3 = 6 by choosing following M packets :

{3, 4, 9, 7, 9}.

Example 2:

Input:

N = 7, M = 3

A = {7, 3, 2, 4, 9, 12, 56}

Output: 2

Explanation: The minimum difference between

maximum chocolates and minimum chocolates

is 4 - 2 = 2 by choosing following M packets :

{3, 2, 4}.

[sliding window of fixed size] Easy solution

class Solution{

   public:

   long long findMinDiff(vector<long long> a, long long n, long long m){

   //code

       sort(a.begin(),a.end());

       long long ans = INT_MAX;

       for(int i=0;i+m<=n;i++) {

           ans = min(ans,a[i+m-1]-a[i]);

       }

       return ans;

   }

};

7.Longest consecutive subsequence

Given an array of positive integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Example 1:

Input:

N = 7

a[] = {2,6,1,9,4,5,3}

Output:

Explanation:

The consecutive numbers here

are 1, 2, 3, 4, 5, 6. These 6

numbers form the longest consecutive

subsquence.

Example 2:

Input:

N = 7

a[] = {1,9,3,10,4,20,2}

Output:

Explanation:

1, 2, 3, 4 is the longest

consecutive subsequence.

int findLongestConseqSubseq(int arr[], int N)

   {

     int ans=0;

     unordered_set<int>s;

     int i=0,j=0;

     for(i=0;i<N;i++)

     {

         s.insert(arr[i]);

     }

     for(i=0;i<N;i++)

     {

         if(s.find(arr[i]-1)==s.end())

         {

             int count =1;

             while(s.find(arr[i]+count)!=s.end())

             {

                 count++;

             }

             ans=max(ans,count);

         }

     }

     return ans;

   }

};

8.Smallest Positive Integer that can not be represented as Sum

Given an array of size N, find the smallest positive integer value that cannot be represented as sum of some elements from the array;

Example 1:

Input:

N = 6

array[] = {1, 10, 3, 11, 6, 15}

Output:

Explanation:

2 is the smallest integer value that cannot

be represented as sum of elements from the array.

Example 2:

Input:

N = 3

array[] = {1, 1, 1}

Output:

Explanation:

1 is present in the array.

2 can be created by combining two 1s.

3 can be created by combining three 1s.

4 is the smallest integer value that cannot be

represented as sum of elements from the array.

class Solution

{

public:

    long long smallestpositive(vector<long long> array, int n)

    {

        // code here

        sort(array.begin(),array.end());

        long long ans=1;

        for(int i=0;i<n&&array[i]<=ans;i++)ans+=array[i];

        return ans;

    }

};

9.Coin Change

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2, .. , SM } valued coins.

Example 1:

Input:

n = 4 , m = 3

S[] = {1,2,3}

Output: 4

Explanation: Four Possible ways are:

{1,1,1,1},{1,1,2},{2,2},{1,3}.

Example 2:

Input:

n = 10 , m = 4

S[] ={2,5,3,6}

Output: 5

Explanation: Five Possible ways are:

{2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5}

and {5,5}.

long long int count(int S[], int m, int n) {

       std::vector<long long> dp(n+1);

       dp[0] = 1;

       for (int i=0; i<m; ++i) {

           for(int j=S[i]; j<=n; ++j) {

               dp[j] += dp[j - S[i]];

           }

       }

       return dp[n];

   }

Longest alternating subsequence

Medium Accuracy: 61.15% Submissions: 8085 Points: 4

A sequence {x1, x2, .. xn} is alternating sequence if its elements satisfy one of the following relations :

x1 < x2 > x3 < x4 > x5..... or x1 >x2 < x3 > x4 < x5.....

Your task is to find the longest such sequence.

Example 1:

Input: nums = {1,5,4}

Output: 3

Explanation: The entire sequenece is a

alternating sequence.

Examplae 2:

Input:

nums = {1,17,5,10,13,15,10,5,16,8}

Ooutput: 7

Explanation: There are several subsequences

that achieve this length.

One is {1,17,10,13,10,16,8}.

int AlternatingaMaxLength(vector<int>&nums){

int in = 1;

int d = 1;

int n = nums.size();

for (int i = 1; i < n; i++) {

if (nums[i - 1] < nums[i])

in = d + 1;

else if (nums[i - 1] > nums[i])

d = in + 1;

}

return max(in, d);

}