Subarray problem

help
1

Problem Statement : Let’s say we have an array A .We have to find longest subarray in which elements greater than x are more than elements not greater than x

I/p : size of array , x
Array elements

Test case : 1
5 5
4 5 7 8 3
Output: 3

Subarray formed : [5,7,8]

2

problem link…?

3

Let’s change the elements larger than x to 1 and the other elements to 0.

Then the problem becomes finding the longest subarray, so that the number of 1 in it is greater than the number of 0.

But here’s a better transition.

Let’s replace 0 above with -1.

Then the problem becomes finding the longest subarray, so that the sum of it is greater than 0.

This becomes a silly problem with an O (n) solution.

2 Likes
4

I found out that this guy seemed to be cheating.:relieved::relieved::relieved:

5

That is why I asked for problem link.
This is common now days: XD

6

This kind of cheating fashion is too bad.

7

I’ve solved the exact same problem 6 months ago. Just convert guys greater than ‘x’ to 1 and others to -1, now find the longest subarray with sum>=0 or sum>=-1 depending on your requirements…
And if you are cheating, then well done!

8

So this problem is not problem of online competition?

9

Not really sure…

10

Karan maze ki baat bolu …this question is from hack with infy…:joy::joy:

11

Really ye approach mere mind me nhi aayi mene sare subarrays banaye( mere bhi ye Wala aaya that)…to 5 hi pass hue out of 9 , but yes… approach is good

12

@loopfree Yes, sadly t is from an ongoing contest. I request you as well to ask for problem links and then only answer the question :stuck_out_tongue: :slight_smile:

13

But ab ho gya …u can discuss now…

14

@loopfree Can you share O(N) solution for finding largest subarray having sum>0

15

n = int(input())
while(n):
l,k = map(int, input().split())
a = list(map(int, input().split()))
print(list(x for x in a if(x >= k)))
a.clear()
n-=1

this is my sample code and if you know simple logic post it

16

Code is cheap, and ideas are the only thing that matters.

First, let’s preprocess the prefix and sum of the array and make it as a S array. it cost O(n) time complexity.

Then we sort S arrays from small to large, obviously the range of S arrays is n, we can use bucket sort, it will take O (n) time complexity.

Let’s start with the smallest value of the S array. Let’s set it to S_i, and record the minimum subscript that appears with a variable p, initial p = n + 1.

So for each current S_i, ans = max(ans, i - p), after each layer of S_i is traversed, p is updated once that p = min(p, i). it will take O (n) time complexity.

So it will take O (n) time complexity.

1 Like
17

Here is my O(nlogn) solution for the problem:- Superior Substring | Practice Problems
Code:-FLGov6 - Online C++0x Compiler & Debugging Tool - Ideone.com

If the problem was :- Find the longest subarray with sum=k, it was possible to do it in O(N) but since it is sum>=k , I only have an O(NlogN) approach for it :slight_smile:

18

Worst case of bucket sort is O(N^2) .

19

I don’t know if the bucket sort we’re talking about is the same thing, but I’m sure there must be an O (n) sort.

21

Timsort has the complexity O(n) for the best case and O(nlogn) for worst. Probably there is no sorting algorithm whose worst case is O(n).