Java Territory: Source Code

Jun 30, 2016

Finding Maximum Subarray, contiguous and non-contiguous

by Manoj Chaudhary / in Algorithm, Interview, Source Code / /

Problem:

Given an array

elements, find the maximum possible sum of a

Contiguous sub-array
Non-contiguous (not necessarily contiguous) sub-array.

Empty sub-arrays/sub-sequences should not be considered.

Solution:

Below is the solution for the problem.

Algorithm
For maximum contiguous elements sum

1) Make sum and previous_sum equal to first element in arrays, a[0].

Now we have to make sure that if sum is negative and Next element is positive, make sum = next element, else add next element to sum. This is done in step 2.

2) Let us assume next element is N, If sum < 0 and N > 0, make sum = N, else make sum = sum + N.

If sum is larger than previous sum, update the previous sum, else if sum < previous sum, and also sum < 0, make sum = next element. This is step 3.

3) If sum >= previous_sum, make previous_sum = sum, else if sum < 0, make sum = N.

4) Repeat steps 2 and 3 for all the elements of input array.

5) Take maximum of sum and previous_sum as the result

For maximum non contiguous elements sum

1) Make sum equal to first element in arrays, a[0].

2) If sum is less than 0 and next element, say N is greater than or equal to 0, make sum =N, else,

3) If sum + N > sum, make sum = sum + N, else,

4) If (sum + N < sum) and (sum < N), make sum = N.

5) Repeat step 2, 3 and 4 for each element in the array.

Program:

public class ContiguousArraySum {

 /**
  * @param a input array
  * @param n number of elements in the array
  * @return returns the array of size 2, element at 0 gives sum of contiguous elements 
         * while element at 1 gives sum of non-contiguous elements.
  */
 private static long[] findSum(int[] a, int n) {
  long[] result = new long[2];
  long contSum = a[0];
  long prevContSum = a[0];
  long nonContSum = a[0];

  for (int i = 1; i < n; i++) {
   if (contSum < 0 && a[i] >= 0) {
    contSum = a[i];
   } else {
    contSum += a[i];
   }
   if (nonContSum < 0 && a[i] >= 0) {
    nonContSum = a[i];
   } else if (nonContSum + a[i] > nonContSum) {
    nonContSum += a[i];
   } else if (nonContSum < a[i] && nonContSum + a[i] < nonContSum) {
    nonContSum = a[i];
   }
   if (contSum >= prevContSum) {
    prevContSum = contSum;
   } else if (contSum < 0) {
    contSum = a[i];
   }
  }

  result[0] = contSum > prevContSum ? contSum : prevContSum;
  result[1] = nonContSum;
  return result;
 }

}

Please post in the comment section if any thing in code is not clear.

Jun 27, 2016

Program to rotate a 2D matrix

by Manoj Chaudhary / in Interview, Source Code / /

Problem

A 2D matrix, A, of dimension m x n. You have to rotate the matrix 1 time in the clockwise direction and print the resultant matrix.

Input Format

First Line: <m>space<n>

Subsequent lines takes Matrix as input.

Example:

Input

3 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Here 3 4 in first line are m(number of rows), and n (number of columns)
Subsequent lines are the Matrix itself.

Expected Output:

5 1 2 3
9 10 6 4
13 11 7 8
14 15 16 12

Program:
Our matrix rotation logic does the following:

Rotate elements of first row
Rotate elements of last column
Rotate elements of last row from the remaining rows
Rotate elements of first column from the remaining rows

Source Code:

public class MatrixRotation {

 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  try {
   // Input number of rows, columns and matrix elements
   int numberOfRows = in.nextInt();
   int numberOfColumns = in.nextInt();
   int matrix[][] = new int[numberOfRows][numberOfColumns];
   for (int i = 0; i < numberOfRows; i++) {
    for (int j = 0; j < numberOfColumns; j++) {
     matrix[i][j] = in.nextInt();
    }
   }

   rotateMatrix(matrix, numberOfRows, numberOfColumns);
   
   // Print rotated matrix
   for (int i = 0; i < numberOfRows; i++) {
    for (int j = 0; j < numberOfColumns; j++) {
     System.out.print(matrix[i][j] + "  ");
    }
    System.out.println();
   }
  } catch (InputMismatchException exception) {
   System.out.println("Invalid input. Only numbers are allowed");
  } finally {
   in.close();
  }
 }

 /**
  * A function to rotate a matrix mat[][] of size M X N.
  * 
  * @param mat matrix of size m x n
  * @param rowSize number of rows in matrix, m
  * @param colSize number of columns in matrix, n
  */
 public static void rotateMatrix(int mat[][], int rowSize, int colSize) {

  // pointers for current row and column
  int currRow = 0;
  int currColumn = 0;
  int prev, curr;

  // p and q defines the number of rows and columns that are not rotated, keeps on decrementing with every iteration
  int p = rowSize;
  int q = colSize;

  while (currRow < p && currColumn < q) {

   if (currRow + 1 == p || currColumn + 1 == q)
    break;

   // store next row's first element, will be copied at first position of current row
   prev = mat[currRow + 1][currColumn];

   // Move elements of first row from the remaining rows
   for (int i = currColumn; i < q; i++) {
    curr = mat[currRow][i];
    mat[currRow][i] = prev;
    prev = curr;
   }
   currRow++;

   // Move elements of last column from the remaining columns
   for (int i = currRow; i < p; i++) {
    curr = mat[i][q - 1];
    mat[i][q - 1] = prev;
    prev = curr;
   }
   q--;

   // Move elements of last row from the remaining rows
   if (currRow < p) {
    for (int i = q - 1; i >= currColumn; i--) {
     curr = mat[p - 1][i];
     mat[p - 1][i] = prev;
     prev = curr;
    }
   }
   p--;

   // Move elements of first column from the remaining rows
   if (currColumn < q) {
    for (int i = p - 1; i >= currRow; i--) {
     curr = mat[i][currColumn];
     mat[i][currColumn] = prev;
     prev = curr;
    }
   }
   currColumn++;
  }

 }

Hopefully you liked the article. Please post your queries in the comments sections.