Arrays

Arrays — Collection of the same type of data.

• The array has a contiguous memory location.

Advantages

• Provides O(1) random access

Limitations

• Static memory size

Memory allocation

The address of A[i] = A+ (size of data type) * i; (here A is the base address)

Sub Array

Continues part of the array where the order is maintained. In general, for an array of size n, there are n*(n+1)/2 non-empty subarrays.

Conditions:

• Continues (No skips/gaps) — Yes
• Order maintained — Yes

Best possible way:

• The time Complexity — O(n²)
• The space complexity — O(1).

Ex. A-> 1,2,3,4,5,6,7,8,9

• Valid — 2, 3, 4
• Valid — 3, 4
• Invalid — 5, 4, 3
• Invalid— 1, 4

Ex. B-> [1, 2, 3, 4]

Sub Arrays — [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4]

static void generateSubArrays(int arr[], int n) {
  // Picking one element in each outer loop
  for (int i = 0; i < n; i++) {
   for (int j = i; j < n; j++) {
    /*
    Printing the subarray between the current starting point i.e. i and the current
    ending point i.e. j
    */
    for (int k = i; k <= j; k++)
     System.out.print(arr[k] + " ");

    System.out.println();
   }
  }
 }

Sub Sequence

A subsequence is a sequence that can be derived from another sequence by removing zero or more elements, without changing the order of the remaining elements.

• No of the subsequence of the array size N = 2^N

Conditions:

• Continues (No skips/gaps) — No
• Order maintained — Yes

Best possible way:

• The time Complexity —O(2^n).
• The space complexity — O(n).

Ex. A-> 1,2,3,4,5,6,7,8,9

• Valid— [2, 4, 8]
• Valid— [3, 8, 9]
• Invalid— [8, 4, 2]
• Invalid— [8, 5, 2]

Ex. B-> [1, 2, 3, 4]

Sub sequence—[1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4].

static void generateSubsequences(int[] arr, int index,
   ArrayList<Integer> subarray) {

  // Print the subsequences when we reach the end of recursion tree.
  if (index == arr.length) {
   if (subarray.size() > 0) {
    for (int i = 0; i < subarray.size(); i++)
     System.out.print(subarray.get(i) + " ");
    System.out.println();
   } else {
    System.out.println("[]");
   }
  } else {
   // adding the current index into the subsequence and calling the recursive
   // function.
   generateSubsequences(arr, index + 1, subarray);

   subarray.add(arr[index]);

   // not adding the current element into the subsequence.
   generateSubsequences(arr, index + 1, subarray);

   // removing the added index into the subsequence.
   subarray.remove(subarray.size() - 1);
  }
  return;
 }

Sub Set

The element present in the subset should belong to the array. The subset does not contain duplicate elements.

Conditions:

• Continues (No skips/gaps) — No
• Order maintained — No
• Duplicate values — No

Best possible way:

• The time Complexity — O(n²)
• The space complexity — O(1).
• Algorithm — general power set algorithm.

ex. A-> 1,2,3,4,5,6,7,8,9,6

• Valid —[ 1, 3] & [3, 1] & [9,1]
• Not valid — 2,6,7,9,6

static void generateSubsets(int arr[], int n) {
  // calculating the power set for the array.
  long powerSet = (long) Math.pow(2, n);

  // Running a counter loop form 0 to to powerSet.
  for (int counter = 0; counter < powerSet; counter++) {
   for (int i = 0; i < n; i++) {
    // if the i-th bit is set then print the i-th element
    if ((counter & (1 << i)) > 0)
     System.out.print(arr[i] + " ");
   }
   System.out.println();
  }
 }

Dynamic Array

Flexibility in size with O(1) random access.

ex. ArrayList.

Jagged Arrays

The array of arrays. The length of each array index can differ. Here, the number of rows will be fixed at the declaration time, but you can vary the number of columns.

No of Elements

The total no of elements while

1. Arrangement permutations → n!
2. choose exactly k elements — Order matters → n! / (n-k)!
3. choose exactly k elements — Order doesn’t matter → n! / ((n-k)! * k!)

Questions

Q1: Minimum information from array to determine a unique subarray

A1: Start index and End index

Q2: What is required for O(1) random access.

A2: Contiguous memory allocation.

Q3: Reverse the given array

• Time Complexity — O(N)
• Space Complexity — O(N)

A3:

//Iteration
reverse (a) {
    for(int i = 0; i < n/2; i++) {
        swap(a[i], a[n-1-i]);
    }
}
​
//Recursion
reverse (a) {
    left = 0;
    rigth = n - 1;
    while(left < right) {
        swap(a[left], a[right]);
        left++;
        right--;
    }
}

Q4: Given an array, Rotate it by k steps

• Input — [1, 2, 3, 4, 5, 6, 7, 8, 9]; k = 3
• Output — [7, 8, 9, 1, 2, 3, 4, 5, 6]

A4: The brute force approach will take TC — O(N²)

The best approach is

• Time Complexity — O(N)
• Space Complexity — O(N)

1. Reverse (0, N-1)
2. Reverse (0, K-1) append Reverse(K, n-1)
here K can be calculated by K = K % N

Q5: Rotate the given matrix by 90 degrees

• Time Complexity — O(N*M) => O(N²)
• Space Complexity — O(1)

A5:

//Algo
//A -> Transporse(A) -> Reverse each row
​
transporse(A) {
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < m; j++) {
            swap(A[i][j], A[j][i]);
        }
    }
}
​
soln(A) {
    A = transporse(A);
    for(int i = 0; i < n; i++) {
        reverse(A[i]);
    }
}

Q6: Print the matrix in spiral order

• Time Complexity — O(N*M) => O(N²)
• Space Complexity — O(1)

A6:

//Let n is row and m is column
L = 0;
R = m - 1;
T = 0;
B = n - 1;
​
while (L <= R && T <= B) {
    
    //Printing Top most row
    for(int i = L; i <= R; i++) {
        print(A[T], A[i]);
    }
    T++;
​
    //Printing Right most row
    for(int i = T; i <= B; i++) {
        print(A[i], A[R]);
    }
    R--;
​
    //Printing Bottom most row
    for(int i = R; i >= L; i--) {
        print(A[B], A[i]);
    }
    B--;
​
    //Printing Left most row
    for(int i = B; i >= T; i--) {
        print(A[i], A[L]);
    }
    L++;
    
}

Thanks…

I Am…..

I am a Software Engineer having experience in mobile app development with expertise in Java, Android and Flutter. Interested people can contact me through LinkedIn and Instagram.