CareerCup

This can be done in O(N*log(N)) time using a min-heap or O(N) using a dequeue.

Basically, the algorithm works like this: for each index i in the array computes the longest subarray that ends at position i and satisfies the requested condition.

Now, let's consider we're at index i, and [j ... i-1] is the longest subarray found in the previous iteration (for i-1). In order to compute the subarray for this iteration we need to find the smallest j' >= j such that min(a[j'], .., a[i-1]) + a[i] >= K.

Now, the trick is how to find j' efficiently.
A first approach is to use a min-heap and start with j' = j and then increment j' and remove element a[j'] from heap until the condition holds (or you reach i). Since j is incremented at most N times => there are a total of N calls to heap.remove_element. Since i is incremented N times => there are N calls to heap.insert_element. => final complexity O(N*log(N)).

A second approach, which is a little bit trickier (I suggest getting a pen and paper for this) is using a deque instead of heap. The constructed deque will have these important properties:
- in the front of the deque is index of the minimum element in seq [j..i-1] (just like the heap)
- the second element is the index of the minimum element in the sequence that remains after removing the first minimum along with the elements in front of it;
- and so on.
So basically if dequeue = [m1, m2, ...] then the initial sequence looks like this [j ... m1 ... m2 ... i-1], and:
- m1 is the index of minimum of sequence [j .. i-1],
- m2 is the index of minimum of sequence (m1 .. i-1] (please note that the interval is open at m1)

I won't explain how you perform the operations on the dequeue in order to prserve those properties (try to think them yourself or look at the code / if you have any questions feel free to ask). You have the implementation below for the time-optimal (dequeue) solution. The methods for updating the deque are push(i) - updates the deque by adding element a[i] and popBadMins() which removes minimums from dequeue and returns the new j'.

Friendly advice: If you're not familiar with dequeue trick, I suggest you try to understand it because it proved to be helpful in programming contests.

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

#define MAX_N 10000

struct Sol {
        int st, end;
        Sol(int s, int e) : st(s), end(e) {};
};

int A[MAX_N], N, K;
vector<Sol> sol;
int maxLen = 0;
deque<int> q;

// adds the [st, end] interval to the solution set if it is maximal so far
void update_sol(int st, int end) {
        int len = end - st + 1;
        
        if (len > maxLen) {
                maxLen = len;
                sol.clear();
        }
        
        if (len == maxLen)
                sol.push_back(Sol(st, end));
}

void read_data() {
        cin >> N >> K;
        for (int i = 0; i < N; ++i)
                cin >> A[i];
}

void push(int index) {
        int val = A[index];
        while (!q.empty() && val <= A[q.back()]) 
                q.pop_back();
        q.push_back(index);
}

int popBadMins(int prevStart, int endIndex) {
        int val = A[endIndex];
        int result = prevStart;

        while (!q.empty() && val + A[q.front()] < K) {
                result = q.front();
                q.pop_front();
        }

        return result;
}

void solve() {
        for (int i = 0, j = -1; i < N; ++i) {
                j = popBadMins(j, i);
                push(i);
                update_sol(j+1, i);
        }
}

void print_result() {
        for (int i = 0; i < sol.size(); ++i) {
                const Sol& s = sol[i];
                for (int j = s.st; j <= s.end; ++j)
                        cout << A[j] << " ";
                cout << endl;
        }
}

int main() {
        read_data();
        solve();
        print_result();
        return 0;
}

Note: Didn't test this thoroughly so I might have missed some corner cases.
Oh, and sorry for the long post.

Also Palantir?

And are you looking for a *maximum length* sub-array?

Use two pointers with a min-heap. Everytime when inserting into heap, check if new element + min-element < k. If so, print from begin to end. Update begin to min-element position. Update end to new-element position. If not, add it to heap, update end position.

With code it should be more clear:

int main(void){
	int s=0, e=0, k;
	int a[1000];
	pq<int> p;
	map<int,int> m;
	int n;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		m[a[i]] = i;
	}
	p.push(-1*a[0]);
	p.push(-1*a[1]);
	s = 0;
	e = 1;
	while(e!=n)
	{
		e++;
		int mn = -1*p.top();
		if(mn + a[e] < k)
		{
			for(int i=s;i<e;i++)
				cout << a[i] << " " ;
			cout << endl;
			p.pop();
			s = m[mn]+1;
		}
		p.push(-1*a[e]);
	}
	int mn1 = -1*p.top();
	p.pop();
	int mn2 = -1*p.top();
	if(mn1+mn2 >= k)
	{
		for(int i=s;i<e;i++)
			cout << a[i] << " ";
		cout << endl;
	}
	return 0;
}

I still could not understand the problem. For the first example

suppose k = 4
-4 9 10 4 -3 8 9 -2

Answer should be:
-4 9 10 4 --> -4+9, 9+10, 10+4 are all greater than k=4
-3 8 9 -2 --> -3+8, 8+9, 9+-2 are all greater than k=4

in my opinion. Am I correct?

Suppose A being a subarray which already holds the criteria, and p is the adjacent member to A, currently being checked.

if p+min1 >= k /*and p+min2 >= k*/
add p to the A,
update min1 /*and min2 values. */

where min1 is the smallest member of A
/* min2 is the smallest member of A which is greater than or equal to min1.
*/

O(N)

Still it is not clear
[ -4,9 ]
[9, 10]
[10,4]
[8,9]
[9, -2]

why these sub arrays are not part of answers, is there any constraint on length of sub array ?

Still it is not clear
[ -4,9 ]
[9, 10]
[10,4]
[8,9]
[9, -2]

why theses sub arrays are not part of answers, is there any constraint on length of sub array ?

void PrintMax(int *a, int length, int k)
{
	int start = 0;
	int delta = k-a[start];
	int end = 0;
	int i = 1;
	int maxend = 0;
	int counter=0;
	while(i < length)
	{
		counter++;
		int cur = a[i];
		if(cur >= delta )
		{
			end = i;
			int tempDelta = k-cur;
			if(tempDelta > delta)
				delta = tempDelta;
			i++;
		}
		else
		{
			if(end > maxend)
			{
				cout<<"\n Sub array...";
				for(int j = start;j<=end; j++)
					cout<<" "<<a[j];
			
				  maxend =end;
			}
			start++;
			i = start+1;
			delta = k- a[start];
		}
	}

	if(end > maxend)
	{
		cout<<"\n Sub array...";
		for(int j = start;j<=end; j++)
			cout<<" "<<a[j];		
	}
}

i made a code to work it out .. complexity is surely less than O(n^2) . Please prove my code wrong because i haven't used either min heap or dequeue to solve it . :)

#include <iostream>

using namespace std;
void display(int B[],int n)
{
if(n>1)
{
for(int i=0;i<n;i++)
cout<<B[i]<<" ";
}
cout<<"\n";

}
int main()
{
int A[12]= {1,2,3,4,5,-5,1,2,3,4,5,-5};
int B[10];
int k,i=1;
int check=1;
int min=0,count=1,flag=0;
cout<<"Enter k\n";
cin>>k;
B[0]=A[0];
while(i<12) // 12 is harcoded .. take n instead
{

if(A[min]+A[i]>k) //to check if the condition satisfies
{
if(i>=check) flag=1; //minimum index to counter(to exclude any minimal subset)
if(A[i]<A[min]) //update min position
min=i;
B[count]=A[i];
count++; //total count in sub-array
i++;}
else
{ if(flag==1) //if displayable ( new elements added)
{display(B,count);flag=0;check=i;} // it should not be displayed till the index i is rediscovered again
{min=min+1;B[0]=A[min];i=min+1;count=1;}
}

}
if(flag==1)
display(B,count);
system("pause");
return 0;
}

This is a standard maximum sub array problem, running time O(nlogn):
Algorithm:
_ recurse on the left_array from low to mid
_ recurse on the right_array from mid+1 to high
_ Find maxArray recursively on the mid_array from low to high
_ compare each of the value to k and see which one is bigger than k, return

findMaxArray for mid:
start from mid to low find the largest sum
start from mid + 1 to high find the largest sum
return totalsum and the index of left and right.

Here is the concrete example written in python:

def findMaxSubArray(array,k):
    def helper(array,low,high):
        if high == low:            
            return array[low],low,high
        mid = (low+high)/2
        left_array,left_left_index,left_right_index = helper(array,low,mid)        
        right_array,right_left_index,right_right_index = helper(array,mid+1,high)
        mid_array,mid_left_index,mid_right_index = findMid(array,low,mid,high)
        if left_array >= k:
            return left_array,left_left_index,left_right_index
        elif right_array >= k:
            return right_array,right_left_index,right_right_index
        elif mid_array >= k:
            return mid_array,mid_left_index,mid_right_index
        else:
            return -1,0,0
    return helper(array,0,len(array)-1)

def findMid(array,low,mid,high):
    left = float("-inf")
    left_sum = 0
    max_left = 0
    max_right = 0
    for i in range(mid,low-1,-1):
        left_sum += array[i]
        if left_sum >= left:
            left = left_sum
            max_left = i
    right = float("-inf")
    right_sum = 0
    for i in range(mid+1,high):
        right_sum += array[i]
        if right_sum >= right:
            right = right_sum
            max_right = i
        else:
            break
    return left + right,max_left,max_right

import random
f = lambda x:-1 if x%3 == 0 else 1
a = [random.randint(0,20)*f(i) for i in range(20)]
print a
print findMaxSubArray(a,20)
print a[findMaxSubArray(a,20)[1]:findMaxSubArray(a,20)[2]]

o(n*logn) for contiguous sub-array:

int array[MAXLEN], size, threshold;

struct info {
  int min;
  int leftend;
  int rightend;
  int mark;
  int count;
};

static int SortFunc(const void *in1, const void *in2) {
  int ind1=*((int*)in1), ind2=*((int*)in2);

  if (array[ind1]<array[ind2]) return 1;
  else if (array[ind1]>array[ind2]) return -1;
  else return 0;
}

void find() {

  struct info *arrayinfo;
  int *arrind, x, y, ind, min, count, left, right, max;

  arrayinfo=(struct info *)malloc(sizeof(struct info)*size);
  arrind=(int *)malloc(sizeof(int)*size);

  bzero(arrayinfo, sizeof(struct info)*size);
  bzero(arrind, sizeof(int)*size);

  for (x=0; x<size; x++) {
    arrind[x]=x;
    arrayinfo[x].leftend=arrayinfo[x].rightend=-1;
  }

  qsort(arrind, size, sizeof(int), SortFunc);

  for (x=0; x<size; x++) {
    ind=arrind[x];
    if ((ind==0 || arrayinfo[ind-1].mark==0) && (ind==size-1 || arrayinfo[ind+1].mark==0)) {
      arrayinfo[ind].mark=1;
      arrayinfo[ind].count=0;
      arrayinfo[ind].leftend=ind;
      arrayinfo[ind].rightend=ind;
      arrayinfo[ind].min=array[ind];
    }
    else {
      if (ind>0 && arrayinfo[ind-1].mark==1 && array[ind]+arrayinfo[ind-1].min > threshold) {
        min=(array[ind] > arrayinfo[ind-1].min) ? arrayinfo[ind-1].min : array[ind];
        left=arrayinfo[ind-1].leftend;
        if (arrayinfo[ind-1].count==0)
          count=2;
        else count=arrayinfo[ind-1].count+1;

        arrayinfo[ind].mark=1;
        arrayinfo[ind].leftend=arrayinfo[ind-1].leftend;
        arrayinfo[ind].rightend=ind;
        arrayinfo[ind].min=min;
        arrayinfo[ind].count=count;
        arrayinfo[left].rightend=ind;
        arrayinfo[left].min=min;
        arrayinfo[left].count=count;
      }

      if (ind<size-1 && arrayinfo[ind+1].mark==1 && array[ind]+arrayinfo[ind+1].min > threshold) {
        min=(array[ind] > arrayinfo[ind+1].min) ? arrayinfo[ind+1].min : array[ind];
        right=arrayinfo[ind+1].rightend;
        if (arrayinfo[ind].count==0) {
          if (arrayinfo[ind+1].count==0)
            count=2;
          else count=arrayinfo[ind+1].count+1;
        }
        else if (arrayinfo[ind+1].count==0)
          count=arrayinfo[ind].count+1;
        else count=arrayinfo[ind].count+arrayinfo[ind+1].count;

        if (arrayinfo[ind].leftend==-1) {
          left=ind;
          arrayinfo[ind].leftend=ind;
        }
        else left=arrayinfo[ind].leftend;

        arrayinfo[ind].mark=1;
        arrayinfo[left].min=min;
        arrayinfo[left].count=count;
        arrayinfo[left].rightend=arrayinfo[ind+1].rightend;
        arrayinfo[right].leftend=arrayinfo[ind].leftend;
        arrayinfo[right].min=min;
        arrayinfo[right].count=count;
      }
    }
  }

  max=-1;
  for (x=0; x<size; x++)
    if (arrayinfo[x].count>max) max=arrayinfo[x].count;

  for (x=0; x<size; x++)
    if (arrayinfo[x].count==max) break;

  right=arrayinfo[x].rightend;
  for (; x<=right; x++) 
    printf(" %d", array[x]);
  printf("\n");

  free(arrind);
  free(arrayinfo);
}

This comment has been deleted.

We can sort the array in n log(n) time and then for each element 'a' in the array we can use binary search to find 'k-a' in the array in log(n) time...even if we dont find the 'k-a' the elements on the right of the index at the end of the search would have sum greater than k....the order of the algo will be n log(n).

If it's just to find "one" sub-array, it's easy. Just parse the array and find the two largest numbers. Then check if the sum of these two largest numbers is greater than k, return these two numbers if it does. o(N)

If it's to find the sub-array with most elements which satisfies this condition, it'll need slightly more work. o(NlogN)
.

sort the array to make it in descending order.

for x in 1..n-1
    if (a[x]+a[x-1]) <= k) break;

if x>=1
  for y in 0..x
     print a[y];

Easy solution - Remember, you can only have one element in the sub-array be less than half of 'k,' and when that happens the other elements have to be big enough to accommodate.

The worst case for my solution is '2n', where 'n' is the length of the longest subarray. The worst case happens when the smallest element is at the tail of the subarray.

find(array, k)
{
	int minimumSize = ceiling(k/2);//Assuming an array of integers. 
	int bestStart = 0;//Start of longest subarray
	int bestEnd = 0;//End of longest subarray
	int bestLength = 0;//Length of longest subarray
	int currentStart = 0;
	int currentEnd = 0;
	int currentLength = 0;
	bool sequenceEnded = false;
	bool minimumSizeChanged = false;
	int indexOfSmallestElement = 0;

	for (int index = 0; index < array.length; index++)
	{

		if (sequenceEnded == true)
		{
			if (currentLength > bestLength)
			{
				bestStart = currentStart;
				bestEnd = currentEnd;
				bestLength = currentLength;
			}
			sequenceEnded = false;
			currentLength = 0;
			currentStart = index;
			currentEnd = index;		
		}
		if (array[index] >= minimumSize || (minimumSizeChanged && index == indexOfSmallestElement))
		{
			index++;
			currentLength++;
			currentEnd++;
		}
		else if (hasMinimumSizeChanged == false)//Start over with the new minimum size.
		{
			currentEnd = currentStart;
			currentLength = 0;
			index = currentStart;
			hasMinimumSizeChanged = true;
			minimumSize = k - array[index];
			indexOfSmallestElement == index;
		}
		else
		{
			sequenceEnded = true;
			minimumSizeChanged = false;
		}


	}


	if (currentLength > bestLength)
	{
		bestStart = currentStart;
		bestEnd = currentEnd;
		bestLength = currentLength;
	}

}