gevorgk
BAN USERThis approach wouldn't work in following case
10 20 8 7 6 5 4 3 2 1
The problem with it is that if triplet around mid is decreasing, we still need to recurse into both halves, to make sure there were no "break" there (see the case above). And it makes complexity linear in worst case.
Sorting is not an option here.
1. One option is to look for min element, and then again look for min which doesn't equal to found one. Complexity – exactly 2*N comparisions
2. Keep two variables, and compare each element to each of them  still 2*N comparisons
3. Keep two variables as min1 and min2, and then proceed through array as follows – pick 2 elements from array, compare them (1 comparison), and then compare the smallest of those with min1 and min2 (another 2 comparisons) . In this case we will have N/2 * 3 = 1.5*N comparisons. Still O(N), but I guess this is what expected from this problem.
Ashot, of course I'm suggesting to modify it to work with file system. Something like
1. Choose a pivot element
2. Start reading a file, write elements less than pivot into one file, and elements greater than pivot into another file. Depending on position of pivot (less than or greater than K) recurse into one of output files.
Working with files will make it really slow, but there is no other choice here. The only optimisation we can do here is to read an input file by blocks of maximum size which can fit into memory instead of reading one element at a time.
So, basically idea is same as in external sort, when you have to sort a file which doesn't fit in memory.
Well, assuming that using a heap already violates problem statement (remember, we can't store even K elements in memory ?), my solution is follows (also violates the property that file cannot fit in memory)
1. read all numbers into memory
2. Create MAX HEAP out of that elements (O(N))
3. Attention.... Extract MAX K times !
total complexity – O(N) + O(k*logN), memory  O(N)
Using the min heap you'll use less memory ( O(K) ) but algorithm will be O(N*logK), which is greater than O(k*LogN) if K < N (which obviously is).
1 to all commenters in this thread.
1. First of all, the solution posted on top does something weird, but does't solve the problem
2. Max heap will not help here, since problem says that even K elements wouldn't fit in the memory
3. If they would fit, max heap is the solution, not the min heap.
It didn't say that there will be ALL long numbers in file. Need to be more clear about possible number of elements and amount of memory. Anyways,if bit array wouldn't fit into memory as well, we may use trie with string representation of those numbers, which I presume should take a lot less memory, since a lot of numbers would have long common prefixes.
 gevorgk May 09, 2012void printMissing(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
int k = i;
while(arr[k] != (k+1))
{
if( arr[k] < 1  arr[k] > n  arr[k] == arr[arr[k]  1] )
{
arr[k] = 1;
break;
}
std::swap(arr[k], arr[arr[k]  1]);
}
}
for (int i = 0; i < n; ++i)
{
if(arr[i] < 0 )
std::cout << i+1 << " is missing" << std::endl;
}
}

gevorgk
June 08, 2010 int MaxStockGain(int arr[], int size)
{
if(size <= 0)
return 0;
int curMin = arr[0];
int MaxGain = 0;
for(int i = 1; i < size; ++i)
{
if (arr[i] < curMin)
{
curMin = arr[i];
continue;
}
int currGain = arr[i]  curMin;
if(currGain > MaxGain)
{
MaxGain = currGain;
}
}
return MaxGain;
}

gevorgk
June 07, 2010 /// finds largest palindrome which occures in given string
std::string largestPalindrome(const std::string& in)
{
using namespace std;
//every element contains length of palindrome
// ending at this index
vector<int> a;
a.resize(in.size());
std::fill(a.begin(), a.end(), 1);
if(in[0] == in[1])
a[1] = 2;
//initialized to 1
for(int i=2; i < a.size();i++)
{
if(in[i]==in[i1])
a[i]=2;
if(in[i]==in[i2])
a[i]=3;
if(ia[i1]1 >=0)
if(in[i]==in[ia[i1]1])
a[i]=a[i1]+2;
}
int pos = 0, max = 0;
for(int i = 0; i < a.size(); ++i )
{
if( a[i] > max )
{
max = a[i];
pos = i;
}
}
if( max > 1 )
{
return in.substr(posmax+1, max);
}
return "";
}

gevorgk
June 05, 2010
you are using O(Rows+Cols) additional memory, you can avoid that too.
 gevorgk February 09, 2014