Maximum subarray problem

Given a array with -ve and +ve integers, find the sub-array with maximum sum.

Answer :
See John Bentley (1986) Programming Perls Addison Wesley for discussion of various implementations, ranging from brute force, O(n^3), solution which remembers previous sums O(n^2), divide and conquer O(n log(n)) and the linear approach. The book can be downloaded here

See also : V.V. Muniswamy in Design And Analysis Of Algorithms

The below code in python uses the technique described in Muniswamy and Bentley above, using dynamic programming and runs in linear time:

a = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]


def linear_method2():
    maxsofar = 0
    maxhere = 0
    for i in range(0, len(a)):
        maxhere = max(maxhere + a[i], 0)
        maxsofar = max(maxsofar, maxhere)
        print( a[:i+1])
        print( 'maxhere %d maxsofar %d ' % (maxhere, maxsofar) )
    print( maxsofar)

def linear_method1():
    # [a] [b] [c] [d]  [e]  [f] [g] ...
    #      |   |   |    |
    #      L   U  i-1   i           
    L = 0 # lowerbound of the max subarray
    U = 0 # upperbound of the max subarray
    summax = 0 # the current max subarray sum, i.e sum(a[L:U])
    sumcur = 0 # the current sum from L to i-1

    for i in range(0, len(a) ):
        # If introducing the next element increases the maximum sum,
        # then include the element
        if (a[i]+sumcur) > summax and sumcur>0 :
            print( ' (a[i]+sumcur) > summax ')
            U = i
            sumcur += a[i]
            summax = sumcur
        # If the current element cannot be introduced above ( since there are -ve in b/w ),
        # but current element is greater than max sum so far => start from this point
        elif a[i] > summax:
            print( 'a[i] > summax' )
            L=i
            U=i
            summax = sumcur = a[i]
        # increase the current sum
        else:
            sumcur += a[i]
        print( 'sumcur %d summax %d L %d U %d Array %s' % (sumcur, summax, L, U, a[L:U+1]) )
    print('maxsubarray : %s' % a[L:U+1])
    print('sum : %d' % summax)
    
linear_method2()
print('------------')
linear_method1()

See also : http://en.wikipedia.org/wiki/Maximum_subarray_problem

Product Array

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

#include "vector"
#include "iterator"
#include "algorithm"
#include "iostream"
#include "stdlib.h"
using namespace std;

/*
 * Pass 1
   --->
   1 2 3 4 5
       ^
   Pass 2
         <--
   1 2 3 4 5
       ^
*/

void ArrayProduct(vector& array)
{
    const int n = array.size();
    vector product(n);
    int prod = 1;
    for ( int i=0; i    {
        product[i] = prod;
        prod *= array[i];
    }
    prod = 1;
    for ( int i=n-1; i>=0; --i)
    {
        product[i] *= prod;
        prod *= array[i];
    }

    copy ( product.begin(), product.end(),
            ostream_iterator(cout, " ")
         );
}

int main ( int argc, char* argv[])
{
    const int n = atoi(argv[1]);
    vector array(n);
    for ( int i = 1; i<= n; ++i )
        array[i-1] = i;
    ArrayProduct(array);
    return 0;
}

Find the non duplicate element

There is an array in which except one element, all other elements have duplicates, find that non duplicate element.

Answer:

/**
 * An array in which all elements except one are duplicate.,
 * find that element
 * */
#include "vector"
#include "algorithm"
#include "stdio.h"
using namespace std;

/** SOLUTION I 
 * Sort the array - O(n log(n))
 * Find the duplicate - O(n) (single pass)
 * */
void SortAndFind(vector &vec)
{
    // O(n log(n))
    sort(vec.begin(), vec.end() );
    int i = 0;
    int j = i + 1;
    int n = vec.size();
    // O(n)
    for ( i = 0, j = i+1; j < n ; ++j)
    {
        if ( vec[j] != vec[i] )
        {
            if ( (j-i) == 1 )
            {
                /* non duplicate found at j */
                printf("\n Non Duplicate (%s) %d \n", __func__, vec[i]);
                return;
            }
            else
            {
                i=j;
            }
        }
    }
    // the last element is the duplicate
    printf("\n Non Duplicate (%s) %d \n", __func__, vec[n-1]);
}

/** SOLUTION II , better than first solution.
 * Heapify the array - O(n)
 * Remove one element at a time and find the duplicate - O(log(n))
 * This approach is better because there is no need to sort the entire array
 * */
void HeapifyAndFind(vector &vec)
{
    // Create the heap O(n)
    make_heap(vec.begin(), vec.end() );
    // Find the duplicate, by removing one element at a
    // time.
    //
    int i = 0;
    int n = vec.size();
    for ( int j = i+1; j < n; ++j)
    {
        // vec[j-1] is the min element
        make_heap( vec.begin() + i , vec.end() );
        if ( vec[i] != vec[j] )
        {
            if ( (j-i) == 1 )
            {
                /* non duplicate found at j */
                printf("\n Non Duplicate (%s) %d \n", __func__, vec[i]);
                return;
            }
            else
            {
                i=j;
            }
        }

    }
    // the last element is the duplicate
    printf("\n Non Duplicate (%s) %d \n", __func__, vec[n-1]);

}

int main(int argc, char *argv[])
{
    if ( argc > 1 )
    {
        vector vec1(argc-1);
        vector vec2(argc-1);

        for (int i = 1; i <= argc-1; ++i)
        {
            vec1[i-1] = atoi(argv[i]);
            vec2[i-1] = atoi(argv[i]);
        }

        SortAndFind( vec1 );
        HeapifyAndFind( vec2 );
    }
    return 0;
}

Second minimum element in a array

Given an array of n numbers a[1], a[2],..., a[n], find the second minimum number in n + log n comparisons.

Answer:


Initially it seems that this can be done in a single pass,
like finding the min element, but dont be tricked, this is not possible.
For example, if the second min happens first and the min element happens later,
then its not possible, ex: {10, 6, 9, 7, 8, 5}

The answer is in fact is in the question itself,
Build a Min Heap - O(n) time
Remove the Root - O(log(n)) time
Remove the Root again, which happens to be the second min element - O(log(n))

So the total time = n + log(n)


See also:
*Selection Sort technique

Sort an Array of 0s and 1s

How would you sort an array that consists of only zeros and ones in only one pass?
Answer:

Use Quick Sort :

0 1 1 1 0 0 1 0 0 1
^       ^         ^
up     pivot      down

Quick sort will do this in one pass.

Count Sort will do this in two passes.

Distributing 0s and 1s in even and odd positions

Given an array of 0s and 1s, write an algo such that,
- the 0s will occupy the even positions.
- the 1s will occupy the odd positions.
- any extra 0s or 1s should be placed at the end of array
Complexity: linear, in a single pass

Answer:

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

//
//  1 0 1 0 1 1 1
//  i j --> move by step of 2
void Distribute0s1s(vector& a, size_t n)
{
    size_t i = 0, // i will point to the even indices
           j = i+1; // j will point to the odd indices
    for ( ; (i < n) && (j < n) ; )
    {
        // already 0 in even position, move ahead
        if ( a[i] == 0 )
        {
            i += 2;
        }

        // already 1 in odd position, move ahead
        if ( a[j] == 1 )
        {
            j += 2;
        }

        if ( i >=n ) break;
        if ( j >=n ) break;

        // 1 in even pos, 0 in odd pos, swap
        if ( a[i] && !a[j] )
        {
            swap( a[i], a[j] );
            i += 2;
            j += 2;
        }
    }

    if ( i < n )
    {
        // At this point, all the odd positions are enused with 
        // 1s
        j = i + 2;
    }
    else if ( j < n )
    {
        // At this point, all the even positions are enused with 
        // 0s
        i = j;
        j = i + 2;
    }

    // handle the remaining numbers
    while ( j < n )
    {
        if (
                (  ( i % 2 == 0 ) &&  ( a[j] < a[i] )  ) ||
                (  ( i % 2 == 1 ) &&  ( a[j] > a[i] )  )
           )
        {
            swap( a[j], a[i] );
            i += 2;
        }
        j += 2;
    }
}

int main( int argc, char* argv[] )
{
    if ( argc == 1 ) return 0;
    else
    {
        vector a(argc-1);
        for ( int i = 1; i <= argc-1; ++i)
            a[i-1] = atoi(argv[i]);
        cout << "Input :" << endl;
        copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
        cout << endl << "Output :" << endl;
        Distribute0s1s(a, a.size() );
        copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
    }
    return 0xabcdef;

}

Min element in a sorted array

Given an array, which has been sorted in ascending order and rotated, how will you go about
finding the min element in it.

Answer:

Let original array be 10 20 30 40 50 , so on rotation it become 40 50 10 20 30
40 50 10 20 30
 ^  ^
Up Down

up = array.begin();
down = Up+1;

while(down != array.end() )
{
  if(*down < *up ) then *down is the smallest element
  ++up;
  ++down;
}

Intersection of two arrays.

Given two arrays of signed integers, give an approach to find the
intersecting set of the two arrays.

Answer:


Solution 1: O(nlog(n)) solution

void ArrayIntersection(int *a, int*b , size_t sizeA, size_t sizeB)
{
    sort(a,sizeA);
    sort(b,sizeB);
    for(size_t i =0, j=0; i < sizeA && j < sizeB; )
    {
        if (a[i] == b[j])
        {
            /* Add a[i] to output intersection list */
            ++i;++j;
            continue;
        }
        else if (a[i] < b[j] )
        {
            ++i; continue;
        }
        else if (a[i] > b[j] )
        {
            ++j; continue;
        }
    }
}

Solution 2: O(n) solution but requires at least O(n) space.
1. Scan the first array and add the elements to a lookup.
2. Scan the second array and if the element is present in the
lookup then add it to the intersection list.

Subarray with a given sum

Given an array, how will find a subarray with a required sum.

Answer:

Solution 1:
Recursively computing the array sum is one of the options, but no optimal.
The trick is to build the array iteratively from the previous results,
for ex: A[0..4]= a[0..3] + A[4]
Complexity : O(m*n/2)

#include 
#include 
#include 
#include 
using namespace std;

int main(int argc, char *argv[])
{
    if (argc <= 1)
        return -1;

    vector a(argc);
    int s[10][10]={};
    const int n = argc-1;

    for(int i = 1; i< argc; ++i)
        a[i] = atoi(argv[i]);

    copy(a.begin(), a.end(), ostream_iterator(cout, " "));
    cout << endl << "----" << endl;

    for(int i = 1; i<= n; ++i)
        s[i][i] = a[i];

    for ( int i = 1; i <= n; ++i )
    {
        for (int j = i+1; j <=n; ++j)
        {
            s[i][j] = s[i][j-1] + a[j];
            printf("[%d][%d] = %d ", i, j, s[i][j]);
            /* if s[i][j] is the required result print it, 
             * and the sub array is [i,j]
             * */
        }
        printf("\n");
    }
    return 0;
}

Products in an array

There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers.

For example, let consider (6, 3, 1, 2). We need to find these products :

- 6 * 3 * 1 = 18
- 6 * 3 * 2 = 36
- 3 * 1 * 2 = 6
- 6 * 1 * 2 = 12

Answer:

Solution 1:

Find the product of all elements in the array.
for ( i=0 to n-1)
{
  compute product/a[i];
}

Solution 2:
Find the combinations, nCn-1 = n and compute the product for each combination.

Array Rotation

Rotate an n-element vector left by i positions in time proportional to n with just a dozen bytes of extra space. For instance, with n=8 and i=3, the vector abcdefgh is rotated to defghabc

Answer:

Step 1: reverse the array.
abcdefgh -> hgfedcba
Step 2: reverse 0 to n-i-1
hgfedcba -> defghcba
Step 3: reverse n-i to n
defghabc

Data structure for elements of 0 - N-1

Propose a data structure for the following:
- The data structure would hold elements from 0 to N-1.
There is no order on the elements (no ascending/descending order
requirement)

The complexity of the operations should be as follows:
* Initialization - O(1)
* Insertion of an element - O(1)
* Deletion of an element - O(1)
* Finding a element - O(1)
* Deleting all elements - O(1)

answer:

use an array (dynamically alloced) of size n.
and array[n] will indicate the count of an element.

n elements are same in a array

Given an array of 2n elements of which n elements are same and the
remaining n elements are all different. Write a C program to find out the
value which is present n times in the array.

Solution:

1. Sort the array - O(nlog(n))
2. Linear algo to find the dup:

for(int i = 0, j=i+1; j < 2n; ++j)
{
  if( a[j] != a[i] )
  {
     if ( (j-i) == n )
       /* a[i] is the required number */
     else
     {
       /* proceed further */
       i = j;
       j+= 1;
     }
  }
}

Setting row and column to zeros

You are given a 2-dimensional integer array Arr[M][N]. A few of the
elements in this array are zero. Write an algorithm such that if
A[i][j] is zero, all the elements in row i and all the elements in
column j should be set to 0. In other words, if any element is zero,
its entire row and column should be zero.

Answer:

Solution in O(mn) time.

Step 1: Init array[m] = {-1}

Step 2:
for ( i = 0; i< m; ++i )
  for ( j = 0; j < n; ++j)
  {
    if ( matrix[i][j] == 0 )
       array[i] = j;
       break;
  }

Complexity : O(mn)

step 3:
for ( k = 0; k < m; ++k)
{
  if(array[k] != -1)
  {
    for( i = 0; i < m; ++i)
      matrix[k][i] = 0;
    for( i = 0; i < n ; ++i)
      matrix[i][array[k]] = 0;
  }
}

complexity: O(m(m+n))

Total complexity = O(mn) + O(m^2) + O(n)

Sorted Array to Binary Tree

Given a sorted (non-decreasing order) array, write an algorithm to
create a binary tree with minimal height. Do this in O(n).

Answer:

The trick is to add the mid element of the array first, because if the elements are sequentially , then the tree will resemble a linked list.

Node* CreateTree(int* array, size_t begin, size_t end)
{
  if( begin > end )
   return NULL;
  size_t mid = (begin+end) / 2;
  Node* n = CreateNode(array[mid]);
  n->left = CreateTree( array, begin, mid-1 );
  n->right = CreateTree( array, mid+1, end );
  return n;
}

Two numbers in a array that add up to a given number

You are given a array, and a number M. Your goal is to find out which two numbers in the array when added up gives M.

Answer:

Step 1. Sort the array in O(n log (n) )
Step 2. Assuming the number is 50,

Optimization of Step 1:
Instead of sorting the complete array,
- Create the heap
- Remove the root until we hit a number k, such that k >= M
- This will be better than sorting the entire array.

down     up
|         |
10 15 20 30 [50] 90

while ( down < up )
{ 
  if ( a[down] + a[up] > a[num] ) --up;
  else if ( a[down] + a[up] < a[num] ) ++down;
  else /* we found a pair */
}

Permutations

Given n,k, write code to give all permutations of numbers of length 'k', where each 'individual' number can be in the range '1 to n'

Intersection of two arrays

Given two arrays of signed integers, give an approach to find the intersecting set of the two arrays.

sub array with largest sum

You're given an array containing both positive and negative integers and required to find the sub array with the largest sum in O(N) time or rather in single pass.

Answer:

#include 
void FindLargestSubarray( int *a, size_t n)
{
    size_t start = a[0];
    int sum = a[0];
    size_t end = 0;
    int intr_sum = 0;
    for ( int i = 1; i < n; ++i)
    {
        intr_sum += a[i];
        if ( (sum+intr_sum) >= sum )
        {
            sum += intr_sum;
            end = i;
            intr_sum = 0;
        }
        else if ( a[i] > sum )
        {
            start = i;
            end = i;
            sum = a[i];
            intr_sum = 0;
        }
    }
    printf("Start %d End %d Sum %d \n", start, end, sum);
}

int main()
{
    int a1[] = {10, -20, 30, -60, 50, 80, 0, -60};
    int a2[] = {10, 20, 30};
    int a3[] = {-99, -5, -1, -100};
    FindLargestSubarray(a1, sizeof(a1)/sizeof(a1[0]) );
    FindLargestSubarray(a2, sizeof(a2)/sizeof(a2[0]) );
    FindLargestSubarray(a3, sizeof(a3)/sizeof(a3[0]) );
    return 0;
}

K smallest numbers

Given N numbers in an unsorted array, find the K smallest numbers.