Subarray problem

help
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).

22

Maybe you didn’t notice the range n?
and the time complexity of the bucket sorting algorithm I learned is O (max-min+n). Maybe you don’t call it that way?

23

Isn’t range the size of array given to us?

24

The difference between the maximum and minimum values of the numbers in this array is O (n) level.

25

I saw this on hackerearth, it says O(n) time to sort using the bucket sort, but on other websites, worst case is O(n^2).

26

I really can’t understand what the worst case is because I said that the time complexity of bucket sorting depends on the range of numbers. Is there any mistake in my statement?

27

<copy - paste>

Worst-case analysis[edit]

Bucket sort is mainly useful when input is uniformly distributed over a range. When the input contains several keys that are close to each other (clustering), those elements are likely to be placed in the same bucket, which results in some buckets containing more elements than average. The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket, which is typically O(n^{2}) insertion sort, making bucket sort less optimal than O(nog (n)) comparison sort algorithms like Quicksort.

28

Maybe my algorithm is different from what you think. This is my code：

# include <bits/stdc++.h>
using namespace std;

const int N = whatever + 1;
int a[N], vis[N];

int main ()
{
    int n = whatever;
    for (int i = 1; i <= n; ++i) a[i] = rand() % n + 1; // Initialization
    for (int i = 1; i <= n; ++i) ++vis[a[i]];
    for (int i = 1; i <= n; ++i) while (vis[i]) cout << i << " ", --vis[i];
    return 0;
}

Now do you understand what I mean?

29

This is called counting sort imo.
And it is O(n+r) where n is number of elements and r= b-a+1 where a<=arr[i]<=b .

30

Well, now I understand why these guys don’t understand what I’m talking about. In China we call it bucket sorting.

31

I mentioned this in my reply above.

1 Like
32

@l_returns to the rescue :grinning:
Honestly saying I have never used bucket sort before but had a good debate

1 Like