Home » Interview coding problems/challenges

Adjacent are not allowed

Adjacent are not allowed: This is a standard recursion problem featured in EPIC system interview, here we will find the solution of it.
Submitted by Radib Kar, on June 14, 2020

Problem statement

Given a rectangular grid of dimension 2 x N find out the maximum sum such that no two chosen numbers are adjacent, vertically, diagonally or horizontally.

Input

The first line of input contains an integer T denoting the number of test cases.

The first line of each test case is N, number of columns in a grid, grid length.

Next two lines describes the 2*N grid.

Output

Print the output for each test case in a separate line.

Constraints:

1 <= T<= 100
1 <= N<= 100
0 <= elements <= 100

Example:

Input:
Test case: 1
Grid column size: 5
Grid as input:

1 4 5 4 13
2 0 10 2 11

Output:
25

Explanation:

The above grid is like following where many combinations are possible within the constraints.

Few have been shown below,

Since, we have got the maximum sum combination already, I am not considering the other combinations. The maximum sum possible to achieve is 25 which can be achieved from combination 2. (If you have doubt thinking about other combinations might produce better result, feel free to process other combinations too until you get exhausted)

So, the answer will be 25.

Solution Approach

This is a standard recursion problem where we are supposed to either consider one number or not consider that number.

Say, the current element under our processing is: arr[r][c]

So, there are two choice,

1. Select arr[r][c] as part of solution then we need to skip all of arr[r+1][c], arr[r][c+1] and arr[r+1][c+1]
2. Don't select arr[r][c]

If we formulate the recursive function, then it becomes,

f(r,c)  =   maximum(arr[r][c]+f(r,c-2),arr[r][c]+f(r-1,c-2),
    arr[r-1][c]+f(r,c-2),arr[r-1][c]+f(r-1,c-2),
    f(arr,r,c-1,n),f(r-1,c-1));

The above recursion is generally illustrated on basis of assumption that all the indexed are valid.

The above recursion will generate many overlapping sub-problems and hence we need to memorize. Below is the detailed memorization process.

In the main function,

Initialize dp[3][n] with -1 which will store the computed sub-problem result.

Call the recursive function, myrecur(arr,0,0,n)

The function signature is described below,

Function myrecur(int arr[][],int r,int c,int n):
    if(r>=2)
        return 0;
    if(c>=n)
        return 0;
    
    // if already computed
    if(dp[r][c]!=-1)
    return dp[r][c];    
    
    // check for valid index
    if(r+1<2) 
        dp[r][c] = maximum(arr[r][c] + myrecur(arr,r,c+2,n), arr[r][c] + 
        myrecur(arr,r+1,c+2,n), arr[r+1][c] + myrecur(arr,r,c+2,n),
        arr[r+1][c] + myrecur(arr,r+1,c+2,n), myrecur(arr,r,c+1,n),
        myrecur(arr,r+1,c+1,n));
    
    else
        dp[r][c] = maximum(arr[r][c] + myrecur(arr,r,c+2,n), 
        arr[r][c] + myrecur(arr,r+1,c+2,n), myrecur(arr,r,c+1,n),
        myrecur(arr,r+1,c+1,n),INT_MIN,INT_MIN);
    
    end if else
        
        return dp[r][c]  // which is the final maximum sum
    End function

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int dp[3][101];

int maximum(int a, int b, int c, int d, int e, int f)
{
    return max(max(max(a, b), max(c, d)), max(e, f));
}

int myrecur(vector<vector<int> > arr, int r, int c, int n)
{
    if (r >= 2)
        return 0;
    if (c >= n)
        return 0;

    if (dp[r][c] != -1)
        return dp[r][c];

    if (r + 1 < 2) {
        dp[r][c] = maximum(arr[r][c] + myrecur(arr, r, c + 2, n), arr[r][c] + myrecur(arr, r + 1, c + 2, n),
            arr[r + 1][c] + myrecur(arr, r, c + 2, n), arr[r + 1][c] + myrecur(arr, r + 1, c + 2, n),
            myrecur(arr, r, c + 1, n), myrecur(arr, r + 1, c + 1, n));
    }
    else {
        dp[r][c] = maximum(arr[r][c] + myrecur(arr, r, c + 2, n), arr[r][c] + myrecur(arr, r + 1, c + 2, n),
            myrecur(arr, r, c + 1, n), myrecur(arr, r + 1, c + 1, n), INT_MIN, INT_MIN);
    }

    return dp[r][c];
}

int my(vector<vector<int> > arr, int n)
{
    for (int i = 0; i <= n; i++) {
        dp[0][i] = -1;
        dp[1][i] = -1;
        dp[2][i] = -1;
    }
    return myrecur(arr, 0, 0, n);
}

int main()
{
    int t, n, item;

    cout << "Enter Number of test cases" << endl;
    cin >> t;

    for (int i = 0; i < t; i++) {
        cout << "Enter length of the array\n";
        cin >> n;

        vector<vector<int> > arr;

        cout << "Enter the grid\n";
        for (int i = 0; i < 2; i++) {
            vector<int> a;
            for (int j = 0; j < n; j++) {
                cin >> item;
                a.push_back(item);
            }
            arr.push_back(a);
        }

        cout << "maximum sum possible is: " << my(arr, n) << endl;
    }

    return 0;
}

Output

Enter Number of test cases
1
Enter length of the array
5
Enter the grid
1 4 5 4 13
2 0 10 2 11
maximum sum possible is: 25