DSA: SubArray

What is a SubArray?

• A subarray is a sequence of elements within an array that is contiguous. In other words, a subarray is a section of an array that contains consecutive elements in the same sequence as the original array.
• Subarrays can range in length from a single element (also considered a subarray) to the full array. If we have an array [1, 2, 3, 4], some of its subarrays are  [1], [2, 3], [4], [1, 2, 3, 4], etc.
• Subarrays are a commonly used concept in computer science and algorithms. Many problems involving arrays and sequences can be solved using subarray manipulation techniques.

Example:

Let us take a look at a few example to understand the subarray concept.

Question 1:

1. You are given an array of size ‘n’ and n elements of the same array.
2. You must find and print all the subarrays of the given array.
3. Each subarray should be space seperated and on a seperate lines. Refer to sample input and output.

import java.io.*;
import java.util.*;

public class Main{

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];

    for(int i = 0; i < n; i++){
       arr[i] = Integer.parseInt(br.readLine());
    }

    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < arr.length; i++){
       for(int j = i; j < arr.length; j++){
          for(int k = i; k <= j; k++){
            sb.append(arr[k] + "\t");
          }
          sb.append("\n");
       }
    }

    System.out.println(sb);
 }}

Output:

5
1
 2
 3
 4
 5

output:
1	
1	2	
1	2	3	
1	2	3	4	
1	2	3	4	5	
2	
2	3	
2	3	4	
2	3	4	5	
3	
3	4	
3	4	5	
4	
4	5	
5

This Java code reads from the user an integer n, which represents the size of an array. The programme then reads n integers from the user and populates an array arr with these values. The code then generates all possible arr subarrays and outputs them to the console in tab-separated format, with each subarray on a new line.

Question 2:

Given two integer values N and K, the task is to create an array A of N integers such that number of the total positive sum subarrays is exactly K and the remaining subarrays have a negative sum .

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int N = 5; // size of the array
        int K = 3; // required number of positive sum subarrays

        int[] A = new int[N];
        Arrays.fill(A, -1); // initialize the array with -1

        int positiveSumCount = 0;

        for (int i = 0; i < N; i++) {
            if (positiveSumCount < K) {
                A[i] = 1;
                positiveSumCount++;
            }
        }

        if (positiveSumCount < K) {
            for (int i = 0; i < N; i++) {
                if (A[i] == -1) {
                    A[i] = 1;
                    positiveSumCount++;
                }

                if (positiveSumCount == K) {
                    break;
                }
            }
        }

        if (positiveSumCount > K) {
            for (int i = 0; i < N; i++) {
                if (A[i] == -1) {
                    A[i] = -1;
                    positiveSumCount--;
                }

                if (positiveSumCount == K) {
                    break;
                }
            }
        }

        System.out.println("Array A: " + Arrays.toString(A));
    }
}

The above code:

1. Create an array A of size N with all elements initialized to -1.
2. Initialize a variable positiveSumCount to 0 to keep track of the number of positive sum subarrays.
3. Iterate through the array A from left to right.
4. For each element A[i], check if positiveSumCount is less than K. If it is, set A[i] to 1 and increment positiveSumCount.
5. If positiveSumCount is equal to K, set the remaining elements of A to -1.
6. If after setting all remaining elements to -1, positiveSumCount is still less than K, set the remaining elements to 1 to create negative sum subarrays.
7. If after setting all remaining elements to 1, positiveSumCount is still greater than K, set the remaining elements to -1 to create negative sum subarrays.

Note: also read about Array Carry Forward

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py