Categories: Data Structure

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

Recent Posts

Generate Parenthesis | Intuition + Code | Recursion Tree | Backtracking | Java

Problem Statement: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example…

2 months ago

Square Root of Integer

Given an integer A. Compute and return the square root of A. If A is…

1 year ago

Build Array From Permutation

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where…

1 year ago

DSA: Heap

A heap is a specialized tree-based data structure that satisfies the heap property. It is…

1 year ago

DSA: Trie

What is a Trie in DSA? A trie, often known as a prefix tree, is…

1 year ago

Trees: Lowest Common Ancestor

What is the Lowest Common Ancestor? In a tree, the lowest common ancestor (LCA) of…

1 year ago