The Algo Blog

Searching a sorted 2D array

A 2D Array is sorted on its row and columns, find a key.

"""
Program to search an element in a 2-d array
The 2D array has sorted rows and sorted columns
"""
from random import randrange

N=10 # we will generate a NxN array

# initializes a 2-d array sorted on rows and columns
ARRAY = [ [i for i in range(j,N+j)] for j in range(N) ]

KEY = randrange(0,ARRAY[N-1][N-1])

# We will skip the brute force method of O(n^2) 

# Attempt 1 : Use binary search
def binary_search(lst, l, u, key):
    if l > u : return -1;
    m = (l+u)/2
    if lst[m] == key: return m
    if lst[m] < key: return binary_search(lst, m+1,u, key)
    else : return binary_search(lst, l, m-1,key)


def binsearch_method():
    "Use binary search on each row : takes loglinear time: O( n log(n) )"
    for i in range(N):
        idx = binary_search(ARRAY[i],0,len(ARRAY[i])-1,KEY)
        if idx != -1:
            print("found %d at %d,%d" % (KEY, i,idx))
            return

def linear_method():
    "search in linear time"
    currow = 0
    curcol = N-1
    steps = 0
    while curcol > 0 and currow < N:
        steps += 1
        #print(currow, curcol)
        # If the elem in a col is greater than key, we can skip the entire col
        if ARRAY[currow][curcol] > KEY: curcol -= 1 
        # If the first element in a row is > than key or if the last elem is < key, we skip the entire row.
        if ARRAY[currow][0] > KEY or ARRAY[currow][curcol] < KEY: currow += 1
        if ARRAY[currow][curcol] == KEY:
            print("found %d at %d,%d in %d steps" % (KEY, currow,curcol, steps) )
            return

if __name__ == "__main__":
    print("Key is %d" % KEY )
    binsearch_method()
    linear_method()

Celebrity is a person whom everybody knows but he knows nobody. You have gone to a party. There are total n persons in the party. Your job is to find the celebrity in the party. You can ask questions of the form Does Mr. X know Mr. Y ?. You will get a binary answer for each such question asked. Find the celebrity by asking only O(n) questions.

References : Python Algorithms: Mastering Basic Algorithms in the Python Language pp.85-86 By Magnus Lie Hetland

Solution (in python):

####

from random import randrange
# Number of persons
N = 100
# the graph of connections built using random values.
G = [ [randrange(2) for i in range(N)] for i in range(N) ]

def create_celebrity():
    C = randrange(N)
    # ensure that we have celebrity at C
    for i in range(N):
        G[i][C] = 1
        G[C][i] = 0
    print("rand celeb : %d" % C)


def bruteforce():
    """Brute force solution to the celebrity problem"""
    n = len(G)
    steps = 0
    for i in range(N):
        is_celeb = 1
        for j in range(N):
            steps += 1
            if i == j: continue
            # i knows j and is not a celebrity
            # j does not know i, break
            if G[i][j] or not G[j][i]: 
                is_celeb = 0;
                break 
        if is_celeb:
            print("found celeb at %d in %d steps" % (i, steps) )
            return i

def bruteforce_improved():
    """Improvement to brute force"""
    # At every-step we can eliminate either i or j
    u,v = 0,1
    steps = 0
    while u < N and v < N:
        steps += 1
        if u == v: v = u+1
        # if u knows v, then u is not a celeb, 
        # if u does not know v, then v is not a celeb
        if G[u][v]: u = u+1
        else : v = v+1
    print("found celeb at %d in %d steps" % (u, steps) )

def linear_time():
    """ finds in linear time : see : 
        Python Algorithms: Mastering Basic Algorithms in the Python Language p.86
        By Magnus Lie Hetland
    """
    u,v = 0,1 # the first two persons
    steps = 0
    # c corresponds to the third to the last person...
    for c in range(2, N):
        steps += 1
        if G[u][v]: u=c # u knows v, replace u
        else:       v=c # otherwise, u is a candidate

    if v==c : c=u #if v has reached end of list, use u.
    else:     c=v

    for i in range(N):
        if c==i: continue
        if G[c][i]:break
        if not G[i][c]: break
    else:
        print("found celeb at %d in %d steps" % (c, steps) )



if __name__ == '__main__':
    create_celebrity()
    bruteforce()
    bruteforce_improved()
    linear_time()

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

Searching a sorted 2D array

The Celebrity Puzzle

Maximum subarray problem