Length of longest increasing circular subarray

0 0 9 minutes read

Given an array containing n numbers. The problem is to find the length of the longest contiguous subarray in a circular manner such that every element in the subarray is strictly greater than its previous element in the same subarray. Time Complexity should be O(n).

Examples:

Input : arr[] = {2, 3, 4, 5, 1}
Output : 5
{2, 3, 4, 5, 1} is the subarray if we circularly
start from the last element and then take the
first four elements. This will give us an increasing
subarray {1, 2, 3, 4, 5} in a circular manner.

Input : arr[] = {2, 3, 8, 4, 6, 7, 10, 12, 9, 1}
Output : 5

Method 1 (Using extra space): Make a temp[] array of size 2*n. Copy the elements of arr[] in temp[] two times. Now, find length of Longest increasing subarray in temp[].

Method 2 (Without using extra space):

Following are the steps:

If n == 1, return 1.

Find length of longest increasing subarray starting with first element of arr[]. Let its length be startLen.

Starting from the next element where the first increasing subarray ends, find the length of the longest increasing subarray. Let it be max.

Consider the length of the increasing subarray that ends with the last element of arr[]. Let it be endLen.

If arr[n-1] < arr[0], then endLen = endLen + startLen.

Finally, return maximum of (max, endLen, startLen).

Implementation:

C++

// C++ implementation to find length of longest
// increasing circular subarray
#include <bits/stdc++.h>
using namespace std;
 
// function to find length of longest
// increasing circular subarray
int longlenCircularSubarr(int arr[], int n)
{
    // if there is only one element
    if (n == 1)
        return 1;
 
    // 'startLen' stores the length of the longest
    // increasing subarray which starts from
    // first element
    int startLen = 1, i;
    int len = 1, max = 0;
 
    // finding the length of the longest
    // increasing subarray starting from
    // first element
    for (i = 1; i < n; i++) {
        if (arr[i - 1] < arr[i])
            startLen++;
        else
            break;
    }
 
    if (max < startLen)
        max = startLen;
 
    // traverse the array index (i+1)
    for (int j = i + 1; j < n; j++) {
 
        // if current element if greater than previous
        // element, then this element helps in building
        // up the previous increasing subarray encountered
        // so far
        if (arr[j - 1] < arr[j])
            len++;
        else {
 
            // check if 'max' length is less than the length
            // of the current increasing subarray. If true,
            // then update 'max'
            if (max < len)
                max = len;
 
            // reset 'len' to 1 as from this element
            // again the length of the new increasing
            // subarray is being calculated
            len = 1;
        }
    }
 
    // if true, then add length of the increasing
    // subarray ending at last element with the
    // length of the increasing subarray starting
    // from first element - This is done for
    // circular rotation
    if (arr[n - 1] < arr[0])
        len += startLen;
 
    // check if 'max' length is less than the length
    // of the current increasing subarray. If true,
    // then update 'max'
    if (max < len)
        max = len;
 
    return max;
}
 
// Driver program to test above
int main()
{
    int arr[] = { 2, 3, 4, 5, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length = "
         << longlenCircularSubarr(arr, n);
    return 0;
}

Java

// Java implementation to find length
// of longest increasing circular subarray
 
class Circular
{
    // function to find length of longest
    // increasing circular subarray
    public static int longlenCircularSubarr(int arr[], 
                                               int n)
    {
        // if there is only one element
        if (n == 1)
            return 1;
 
        // 'startLen' stores the length of the 
        // longest increasing subarray which 
        // starts from first element
        int startLen = 1, i;
        int len = 1, max = 0;
 
        // finding the length of the longest
        // increasing subarray starting from
        // first element
        for (i = 1; i < n; i++) {
            if (arr[i - 1] < arr[i])
                startLen++;
            else
                break;
        }
 
        if (max < startLen)
            max = startLen;
 
        // traverse the array index (i+1)
        for (int j = i + 1; j < n; j++) {
 
            // if current element if greater than
            // previous element, then this element 
            // helps in building up the previous 
            // increasing subarray encountered so far
            if (arr[j - 1] < arr[j])
                len++;
            else {
 
                // check if 'max' length is less than 
                // the length of the current increasing 
                // subarray. If true, then update 'max'
                if (max < len)
                    max = len;
     
                // reset 'len' to 1 as from this element
                // again the length of the new increasing
                // subarray is being calculated
                len = 1;
            }
        }
 
        // if true, then add length of the increasing
        // subarray ending at last element with the
        // length of the increasing subarray starting
        // from first element - This is done for
        // circular rotation
        if (arr[n - 1] < arr[0])
            len += startLen;
 
        // check if 'max' length is less than the 
        // length of the current increasing subarray. 
        // If true, then update 'max'
        if (max < len)
            max = len;
 
        return max;
    }
     
    // driver code
    public static void main(String[] args)
    {
        int arr[] = { 2, 3, 4, 5, 1 };
        int n = 5;
        System.out.print("Length = "+ 
                      longlenCircularSubarr(arr, n));
    }
}
 
// This code is contributed by rishabh_jain

Python3

# Python3 implementation to find length
# of longest increasing circular subarray
 
# function to find length of longest
# increasing circular subarray
def longlenCircularSubarr (arr, n):
     
    # if there is only one element
    if n == 1:
        return 1
     
    # 'startLen' stores the length of the 
    # longest increasing subarray which
    # starts from first element
    startLen = 1
     
    len = 1
    max = 0
     
    # finding the length of the longest
    # increasing subarray starting from
    # first element
    for i in range(1, n):
        if arr[i - 1] < arr[i]:
            startLen+=1
        else:
            break
     
    if max < startLen:
        max = startLen
         
    # traverse the array index (i+1)
    for j in range(i + 1, n):
         
        # if current element if greater than
        # previous element, then this element 
        # helps in building up the previous 
        # increasing subarray encountered 
        # so far
        if arr[j - 1] < arr[j]:
            len+=1
        else:
            # check if 'max' length is less 
            # than the length of the current
            # increasing subarray. If true,
            # then update 'max'
            if max < len:
                max = len
             
            # reset 'len' to 1 as from this 
            # element again the length of the
            # new increasing subarray is 
            # being calculated
            len = 1
             
    # if true, then add length of the increasing
    # subarray ending at last element with the
    # length of the increasing subarray starting
    # from first element - This is done for
    # circular rotation
    if arr[n - 1] < arr[0]:
        len += startLen
     
    # check if 'max' length is less than the
    # length of the current increasing subarray.
    # If true, then update 'max'
    if max < len:
        max = len
     
    return max
 
# Driver code to test above
arr = [ 2, 3, 4, 5, 1 ]
n = len(arr)
print("Length = ",longlenCircularSubarr(arr, n))
 
# This code is contributed by "Sharad_Bhardwaj".

C#

// C# implementation to find length
// of longest increasing circular subarray
using System;
 
public class GFG {
 
    // function to find length of longest
    // increasing circular subarray
    static int longlenCircularSubarr(int[] arr, int n)
    {
        // if there is only one element
        if (n == 1)
            return 1;
 
        // 'startLen' stores the length of the longest
        // increasing subarray which starts from
        // first element
        int startLen = 1, i;
        int len = 1, max = 0;
 
        // finding the length of the longest
        // increasing subarray starting from
        // first element
        for (i = 1; i < n; i++) {
            if (arr[i - 1] < arr[i])
                startLen++;
            else
                break;
        }
 
        if (max < startLen)
            max = startLen;
 
        // traverse the array index (i+1)
        for (int j = i + 1; j < n; j++) {
 
            // if current element if greater than previous
            // element, then this element helps in building
            // up the previous increasing subarray encountered
            // so far
            if (arr[j - 1] < arr[j])
                len++;
            else {
 
                // check if 'max' length is less than the length
                // of the current increasing subarray. If true,
                // then update 'max'
                if (max < len)
                    max = len;
 
                // reset 'len' to 1 as from this element
                // again the length of the new increasing
                // subarray is being calculated
                len = 1;
            }
        }
 
        // if true, then add length of the increasing
        // subarray ending at last element with the
        // length of the increasing subarray starting
        // from first element - This is done for
        // circular rotation
        if (arr[n - 1] < arr[0])
            len += startLen;
 
        // check if 'max' length is less than the length
        // of the current increasing subarray. If true,
        // then update 'max'
        if (max < len)
            max = len;
 
        return max;
    }
 
    // Driver program to test above
    static public void Main()
    {
        int[] arr = { 2, 3, 4, 5, 1 };
        int n = arr.Length;
        Console.WriteLine("Length = " +
                           longlenCircularSubarr(arr, n));
        // Code
    }
}
 
// This code is contributed by vt_m.

PHP

<?php 
// PHP implementation to find length of longest
// increasing circular subarray
 
// function to find length of longest
// increasing circular subarray
function longlenCircularSubarr(&$arr, $n)
{
    // if there is only one element
    if ($n == 1)
        return 1;
 
    // 'startLen' stores the length of the longest
    // increasing subarray which starts from
    // first element
    $startLen = 1;
    $len = 1;
    $max = 0;
 
    // finding the length of the longest
    // increasing subarray starting from
    // first element
    for ($i = 1; $i < $n; $i++) 
    {
        if ($arr[$i - 1] < $arr[$i])
            $startLen++;
        else
            break;
    }
 
    if ($max < $startLen)
        $max = $startLen;
 
    // traverse the array index (i+1)
    for ($j = $i + 1; $j < $n; $j++) 
    {
 
        // if current element if greater than 
        // previous element, then this element 
        // helps in building up the previous 
        // increasing subarray encountered
        // so far
        if ($arr[$j - 1] < $arr[$j])
            $len++;
        else
        {
 
            // check if 'max' length is less than 
            // the length of the current increasing 
            // subarray. If true, then update 'max'
            if ($max < $len)
                $max = $len;
 
            // reset 'len' to 1 as from this element
            // again the length of the new increasing
            // subarray is being calculated
            $len = 1;
        }
    }
 
    // if true, then add length of the increasing
    // subarray ending at last element with the
    // length of the increasing subarray starting
    // from first element - This is done for
    // circular rotation
    if ($arr[$n - 1] < $arr[0])
        $len += $startLen;
 
    // check if 'max' length is less than the length
    // of the current increasing subarray. If true,
    // then update 'max'
    if ($max < $len)
        $max = $len;
 
    return $max;
}
 
// Driver Code
$arr = array( 2, 3, 4, 5, 1 );
$n = sizeof($arr);
echo "Length = " . longlenCircularSubarr($arr, $n);
 
// This code is contributed by ita_c
?>

Javascript

<script>
 
// Javascript implementation to find length
// of longest increasing circular subarray
     
     // function to find length of longest
    // increasing circular subarray
    function longlenCircularSubarr(arr,n)
    {
        // if there is only one element
        if (n == 1)
            return 1;
   
        // 'startLen' stores the length of the 
        // longest increasing subarray which 
        // starts from first element
        let startLen = 1, i;
        let len = 1, max = 0;
   
        // finding the length of the longest
        // increasing subarray starting from
        // first element
        for (i = 1; i < n; i++) {
            if (arr[i - 1] < arr[i])
                startLen++;
            else
                break;
        }
   
        if (max < startLen)
            max = startLen;
   
        // traverse the array index (i+1)
        for (let j = i + 1; j < n; j++) {
   
            // if current element if greater than
            // previous element, then this element 
            // helps in building up the previous 
            // increasing subarray encountered so far
            if (arr[j - 1] < arr[j])
                len++;
            else {
   
                // check if 'max' length is less than 
                // the length of the current increasing 
                // subarray. If true, then update 'max'
                if (max < len)
                    max = len;
       
                // reset 'len' to 1 as from this element
                // again the length of the new increasing
                // subarray is being calculated
                len = 1;
            }
        }
   
        // if true, then add length of the increasing
        // subarray ending at last element with the
        // length of the increasing subarray starting
        // from first element - This is done for
        // circular rotation
        if (arr[n - 1] < arr[0])
            len += startLen;
   
        // check if 'max' length is less than the 
        // length of the current increasing subarray. 
        // If true, then update 'max'
        if (max < len)
            max = len;
   
        return max;
    }
     
     // driver code
    let arr=[2, 3, 4, 5, 1 ];
    let n = 5;
    document.write("Length = "+ 
                      longlenCircularSubarr(arr, n));
     
    // This code is contributed by avanitrachhadiya2155
</script>

Output

Length = 5

Time Complexity: O(n).

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!