A subarray is called alternating if any two consecutive numbers in it have opposite signs (i.e. one of them should be negative, whereas the other should be positive).
Given an array of n integers. For each index i, we need to find the length if the longest alternating subarray starting at i.
Examples:
Input : a[] = {1, -5, 1, -5}
Output : For index 0, {1, -5, 1, -5} = 4
index 1, {-5, 1, -5} = 3
index 2, {1, -5} = 2
index 3, {-5} = 1.
Input :a[] = {-5, -1, -1, 2, -2, -3}
Output : index 0 = 1,
index 1 = 1,
index 2 = 3,
index 3 = 2,
index 4 = 1,
index 5 = 1,
Naive Approach: As per the problem statement we need to find the longest alternating subarray prefix length for every index . So one of the naive way is to start from all the indices i ( i.e., 0 to N-1) and calculate the length of the longest alternating subarray length . While traversing at any point of time if we observe two adjacent elements having the same sign (i.e., either positive or negative ) we need not to proceed further we can break the loop and update the length till the computed index .
Implementation:
C++
#include<bits/stdc++.h>using namespace std;// function which computes the longest alternating subarray prefixvoid computeLength(vector<long> &arr,long n){ // pick each and every index for(long i=0;i<n;i++) { // store the current index long j=i; /* traverse until the last but one index since we are comparing the current element with the next element */ while(j < n-1) { /* if at any point of time if we observe that both of the adjacent elements are having the same sign i.e., either positive or negative or zero we need not to proceed to the next index */ if((arr[j] >= 0 and arr[j+1] >= 0) or (arr[j] < 0 and arr[j+1] < 0)) break; // if not check for the next index since we need longest length j++; } // print the length computed for every index cout << abs(j - i) + 1 << " "; } return ;}int main(){ long n; cin >> n; vector<long> arr(n,0); for(long i=0;i<n;i++) { cin >> arr[i]; } computeLength(arr,n); cout << endl; return 0; } |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG{ // function which computes the longest alternating subarray prefixstatic void computeLength(long[] arr,long n){ // pick each and every index for(long i = 0; i < n; i++) { // store the current index long j=i; /* traverse until the last but one index since we are comparing the current element with the next element */ while(j < n-1) { /* if at any point of time if we observe that both of the adjacent elements are having the same sign i.e., either positive or negative or zero we need not to proceed to the next index */ if((arr[(int)j] >= 0 && arr[(int)j+1] >= 0) || (arr[(int)j] < 0 && arr[(int)j+1] < 0)) break; // if not check for the next index since we need longest length j++; } // print the length computed for every index System.out.printf("%d ",Math.abs(j - i) + 1); } return ;}public static void main(String args[]){ Scanner sc = new Scanner(System.in); long n = sc.nextLong(); long[] arr = new long[(int)n]; for(long i=0;i<n;i++) { arr[(int)i] = sc.nextLong(); } computeLength(arr,n); System.out.println();}}// This code is contributed by shinjanpatra |
Python3
# function which computes the longest alternating subarray prefixdef computeLength(arr, n): # pick each and every index for i in range(n): # store the current index j = i # traverse until the last but one # index since we are comparing the # current element with the next element while(j < n-1): # if at any point of time if we # observe that both of the adjacent # elements are having the same sign # i.e., either positive or negative or zero # we need not to proceed to the # next index if((arr[j] >= 0 and arr[j+1] >= 0) or (arr[j] < 0 and arr[j+1] < 0)): break # if not check for the next index since we need longest length j += 1 # print the length computed for every index print(abs(j - i) + 1,end = " ") return# driver coden = int(input())arr = [0 for i in range(n)]for i in range(n): arr[i] = int(input())computeLength(arr,n)print()# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;public class GFG { // function which computes the longest alternating // subarray prefix static void computeLength(long[] arr, long n) { // pick each and every index for (long i = 0; i < n; i++) { // store the current index long j = i; /* traverse until the last but one index since we are comparing the current element with the next element */ while (j < n - 1) { /* if at any point of time if we observe that both of the adjacent elements are having the same sign i.e., either positive or negative or zero we need not to proceed to the next index */ if ((arr[(int)j] >= 0 && arr[(int)j + 1] >= 0) || (arr[(int)j] < 0 && arr[(int)j + 1] < 0)) break; // if not check for the next index since we // need longest length j++; } // print the length computed for every index Console.Write(Math.Abs(j - i) + 1 + " "); } return; } static public void Main() { // Code long n = Convert.ToInt64(Console.ReadLine()); long[] arr = new long[(int)n]; for (long i = 0; i < n; i++) { arr[(int)i] = Convert.ToInt64(Console.ReadLine()); } computeLength(arr, n); }}// This code is contributed by lokeshmvs21. |
Javascript
<script>// Simple JavaScript program // function which computes the longest alternating subarray prefixfunction computeLength(arr, n){ // pick each and every index for(let i = 0; i < n; i++) { // store the current index let j = i; /* traverse until the last but one index since we are comparing the current element with the next element */ while(j < n - 1) { /* if at any point of time if we observe that both of the adjacent elements are having the same sign i.e., either positive or negative or zero we need not to proceed to the next index */ if((arr[j] >= 0 && arr[j+1] >= 0) || (arr[j] < 0 && arr[j+1] < 0)) break; // if not check for the next index since we need longest length j++; } // print the length computed for every index document.write(Math.abs(j - i) + 1," "); } return ;}// driver codelet n = prompt();let arr = new Array(n).fill(0);for(let i = 0; i < n; i++){ arr[i] = prompt();}computeLength(arr, n);document.write("</br>");// This code is contributed by shinjanpatra</script> |
Input :
6 -5 -1 -1 2 -2 -3
Output :
1 1 3 2 1 1
Time Complexity : O(N^2) .
- For the arrays like [ 1 , -1 , 2 , -1] we will be traversing until the end of the array for each index so the complexity will look like :
- Let us take for a value of N .
- In each iteration we traverse N – i -1 indices where i [ 0, N-1] . So that sums N-1 + N -2 + N – 3 + …. + 1 . This is the sum of N-1 natural numbers the mathematical notation is (N * (N – 1))/2 . If we simplify it further :
- (N^2 – N)/2
- When we are trying to represent the above term in the form of asymptotic notations , we need to drop all the lower terms as well as the coefficients . So the higher term is N ^ 2 , hence it can be represented as O ( N ^ 2) .
Space Complexity : O(1). Since apart from the input array we didn’t use any auxiliary data structures to perform any computations .
Efficient Approach: Observe that when a[i] and a[i+1] have opposite signs, count[i] will be 1 more than count[i+1]. Otherwise when they have same sign count[i] will be 1.
We use Dynamic Programming here.
Implementation:
C++
// CPP program to find longest alternating// subarray starting from every index.#include <bits/stdc++.h>using namespace std;void longestAlternating(int arr[], int n){ int count[n]; // Fill count[] from end. count[n - 1] = 1; for (int i = n - 2; i >= 0; i--) { if (arr[i] * arr[i + 1] < 0) count[i] = count[i + 1] + 1; else count[i] = 1; } // Print result for (int i = 0; i < n; i++) cout << count[i] << " ";}// Driver codeint main(){ int a[] = { -5, -1, -1, 2, -2, -3 }; int n = sizeof(a) / sizeof(a[0]); longestAlternating(a, n); return 0;} |
Java
// Java program to find longest alternating// subarray starting from every index.import java.util.*;class Longest{ public static void longestAlternating(int arr[], int n) { int[] count = new int[n]; // Fill count[] from end. count[n - 1] = 1; for (int i = n - 2; i >= 0; i--) { if (arr[i] * arr[i + 1] < 0) count[i] = count[i + 1] + 1; else count[i] = 1; } // Print result for (int i = 0; i < n; i++) System.out.print(count[i] + " "); } // driver program public static void main(String[] args) { int a[] = { -5, -1, -1, 2, -2, -3 }; int n = 6; longestAlternating(a, n); }}// This code is contributed by rishabh_jain |
Python3
# Python3 program to find longest alternating# subarray starting from every index.def longestAlternating(arr, n) : count = [None] * n # Fill count[] from end. count[n - 1] = 1 i = n - 2 while i >= 0 : if (arr[i] * arr[i + 1] < 0) : count[i] = count[i + 1] + 1 else : count[i] = 1; i = i - 1 i = 0 # Print result while i < n : print (count[i], end = " ") i = i + 1# Driver Codea = [ -5, -1, -1, 2, -2, -3 ]n = len(a)longestAlternating(a, n);# This code is contributed by rishabh_jain |
C#
//C# program to find longest alternating// subarray starting from every index.using System;class Longest{ public static void longestAlternating(int []arr, int n) { int[] count = new int[n]; // Fill count[] from end. count[n - 1] = 1; for (int i = n - 2; i >= 0; i--) { if (arr[i] * arr[i + 1] < 0) count[i] = count[i + 1] + 1; else count[i] = 1; } // Print result for (int i = 0; i < n; i++) Console.Write(count[i] + " "); } // Driver program public static void Main() { int []a = { -5, -1, -1, 2, -2, -3 }; int n = 6; longestAlternating(a, n); }}// This code is contributed by vt_m |
PHP
<?php// PHP program to find longest alternating// subarray starting from every index.function longestAlternating( $arr, $n){ $count = array(); // Fill count[] from end. $count[$n - 1] = 1; for ( $i = $n - 2; $i >= 0; $i--) { if ($arr[$i] * $arr[$i + 1] < 0) $count[$i] = $count[$i + 1] + 1; else $count[$i] = 1; } // Print result for ( $i = 0; $i < $n; $i++) echo $count[$i] , " ";} // Driver code $a = array( -5, -1, -1, 2, -2, -3 ); $n =count($a); longestAlternating($a, $n);// This code is contributed by anuj_67.?> |
Javascript
<script>// JavaScript program to find longest alternating // subarray starting from every index. function longestAlternating(arr, n) { let count = new Array(n); // Fill count[] from end. count[n - 1] = 1; for (let i = n - 2; i >= 0; i--) { if (arr[i] * arr[i + 1] < 0) count[i] = count[i + 1] + 1; else count[i] = 1; } // Print result for (let i = 0; i < n; i++) document.write(count[i] + " "); } // Driver code let a = [ -5, -1, -1, 2, -2, -3 ]; let n = a.length; longestAlternating(a, n); // This code is contributed by Surbhi Tyagi.</script> |
Output
1 1 3 2 1 1
Time Complexity: O(N), where N represents the size of the given array.
Auxiliary Space: O(N), where N represents the size of the given array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
