Problem

Submissions

Hints & solutions

Discuss

Longest Alternating Subarray

Easy

0/40

Average time to solve is 25m

Contributed by

1 upvote

Problem statement

You are given a 0-indexed array of integers ‘NUMS’ of length ‘N’. For each index ‘i’ ( i >=0 & i < ‘N’ ) find the length of the longest subarray starting from ‘i’.

Alternating subarray is a subarray in which the adjacent numbers are of different signs.

Example:

Input: ‘N’ = 5,  ‘NUMS’ = {-1, 2, 3, -5, 2}.

Output: {2, 1, 3, 2, 1}.

The longest alternating subarray starting from index 0 is -1, 2.
The longest alternating subarray starting from index 1 is 2.
The longest alternating subarray starting from index 2 is 3, -5 2.
The longest alternating subarray starting from index 3 is -5, 2.
The longest alternating subarray starting from index 4 is 2.
Hence, the final output array is {2, 1, 3, 2, 1}.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the length of the array ‘NUMS. 

The second line of each test case contains ‘N’ space-separated integers.

Output format :

For each test case, you don’t need to print anything just return an array containing the longest alternating subarray starting from each index of the array ‘NUMS’.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5 
-10^6 <= NUMS[ i ] <= 10^6
Sum of N Over all the Test cases <= 10^5

Time Limit: 1 sec

Sample Input 1 :

2
5
-1 -1 2 -1 2
3
-2 -2 -2

Sample Output 1 :

1 2 3 2 1
1 1 1

Explanation Of Sample Input 1 :

For the first case:
The longest alternating subarray starting from index 0 is -1.
The longest alternating subarray starting from index 1 is -1, 2.
The longest alternating subarray starting from index 2 is 2, -1, 2.
The longest alternating subarray starting from index 3 is -1, 2.
The longest alternating subarray starting from index 4 is 2.
Hence, the final array is [1, 2, 3, 2, 1].



For the second case:
Since all the elements have the same signs so at most 1 length subarray is possible for all.
Hence, the final array is [1, 1, 1].

Sample Input 2 :

2
6
-15 100 23 -23 1 15
7
101 110 123 -11 -12 1 -2

Sample Output 2 :

2 1 3 2 1 1 
1 1 2 1 3 2 1

Hint 1

Hint 2

Can you think of a way to solve this problem using two nested loops?

Approaches (2)

Approach 1

Approach 2

BruteForce

In this approach, from each index, we can run a nested loop to find the longest alternating subarray.

The steps are as follows:-

Function longestAlternatingSubarray( [ int ] nums):

Initialize an array 'ANS' of length 'N' with value 1.
Run a loop from 'i' = 0...'N' - 1:
- Initialize a variable 'curLen' with a value of 1.
- Run a loop from 'j' = 'i' + 1... 'N' - 1:
  - If the signs of value of 'NUMS' at 'j' and 'j-1' are not the same then increment the value of 'curLen' by 1.
  - Else break out the loop.
- Assign the value of 'curLen' to 'ANS' at index 'i'.
Return the 'ANS' array.

Time Complexity

O( N ^ 2 ), Where ‘N’ is the length of the array ’NUMS’.

For each index, we are running a nested loop to find the longest alternating subarray.

Hence the time complexity is O( N ^ 2 ).

Space Complexity

O( 1 ),

We are not using any extra space. space required for the ‘ANS’ array can be ignored.

Hence space complexity is O( 1 ).

(100% EXP penalty)

Longest Alternating Subarray

Console