Question

Let A = [A[1], A[2],…..,A[n]] be an array of n distinct integers. For 1 <= j <= n, the index j is a happy index if A[i] < A[j] for all 1 <= i < j. Describe an O(n)- time algorithm that finds all the happy indices in the array A. Partial credit will be given for an O(n log(n))-time algorithm and a minimal credit will be given for an O(n^2) –time algorithm. What is the running time of your algorithm? Justify the correctness of your algorithm and your complexity claim.

Answer 1

Note* Here indices are starting from 1.I am considering the first index as always happy as there are no element before the 1st number.In the code given below it starts with A[0] as programming languages index starts from 0.So please dont get confused A[n-1] in program is same as A[n] in question.The output is as required that it the output is in accordance with the question asked.It will be from 1 to n.

A = [A[1],A[2],A[3],....................A[n]]

Index j take values from 1 to n.

Index j is happy index if for all i < j A[i]<A[j]

I am providing a O(n) complexity here.

Method :

We initialize a variable called maximum which maintains the maximum upto the previous element while we are checking for jth element.If our element at jth index is greater than this maximum then it is a good index because as it is greater than the maximum number so it will be greater than all other numbers.And we update the maximum to this element and proceed to check whether j+1th index number is a good index or not.If this is not greater than the maximum number then it is not a good index and we dont this value into our happyindex list.We proceed with the net number.

Python code:

#defining main function
def main():
A = [] # List which ill have all numbers
happy = [] # list of all happy indices
x = int(input("enter number of values in the array")) # taking number of values in the list
for i in range(x): # a for loop for taking aall the inputs
y = int(input("enter a value"))
A.append(y)
maximum = A[0] # initializing maximum variable to A[0] which is the first value.this means
#A[1] in our program where our indexing starts from 1
happy.append(1) # because there is no element before 1st number
for i in range(1,x): # checking if each index is a happy index
if A[i] > maximum: # checking the condition
happy.append(i+1) # if greater than append it
maximum = A[i] # set the new maximum
else:
continue # continue with other index
print("The happy index are" + str(happy)) # print the result

# calling the main function
if __name__ == "__main__":
main()

Picture for indentation :

Screenshot of the result for a sample array :

Running time for the algorithm : O(n)

Correctness of our algorithm :

In the second for loop used to check whether the index is correct we are comparing it with the maximum upto j-1.So if jth index value is greater than this maximum then it definitely means that it is greater than all the values before it.By definition it is a happy index and we update the maximum for the next case.So all the values that we are appending in the list will be happy values.

Pre condition : N > 0 i.e we will be provided with atleast one number and A[i] != A[j] for all i and j in range 1 to n both inclusive and i!=j.

Post condition : happy list is of all index which are happy

Program terminates as we check for at maximum n elements.

Loop variant (second loop) : if we are checking for jth element then maximum is the maximum of elements upto j-1.

From loop invariant and the argument we did before we achieve post condition.So our program is correct.

Expanation :

We can see that we used only two for loops and this for loops are not nested they are in parllel and all other program statements take constant time.This for loop takes O(n) time.So our program running time complexity is O(n).

Answer 2

Please comment if you have any doubt regarding this question.I will solve your doubts as soon as possible.Thank you.

Note* Here indices are starting from 1.I am considering the first index as always happy as there are no element before the 1st number.In the code given below it starts with A[0] as programming languages index starts from 0.So please dont get confused A[n-1] in program is same as A[n] in question.The output is as required that it the output is in accordance with the question asked.It will be from 1 to n.

A = [A[1],A[2],A[3],....................A[n]]

Index j take values from 1 to n.

Index j is happy index if for all i < j A[i]<A[j]

I am providing a O(n) complexity here.

Method :

We initialize a variable called maximum which maintains the maximum upto the previous element while we are checking for jth element.If our element at jth index is greater than this maximum then it is a good index because as it is greater than the maximum number so it will be greater than all other numbers.And we update the maximum to this element and proceed to check whether j+1th index number is a good index or not.If this is not greater than the maximum number then it is not a good index and we dont this value into our happyindex list.We proceed with the net number.

Python code:

#defining main function
def main():
A = [] # List which ill have all numbers
happy = [] # list of all happy indices
x = int(input("enter number of values in the array")) # taking number of values in the list
for i in range(x): # a for loop for taking aall the inputs
y = int(input("enter a value"))
A.append(y)
maximum = A[0] # initializing maximum variable to A[0] which is the first value.this means
#A[1] in our program where our indexing starts from 1
happy.append(1) # because there is no element before 1st number
for i in range(1,x): # checking if each index is a happy index
if A[i] > maximum: # checking the condition
happy.append(i+1) # if greater than append it
maximum = A[i] # set the new maximum
else:
continue # continue with other index
print("The happy index are" + str(happy)) # print the result

# calling the main function
if __name__ == "__main__":
main()

Picture for indentation :

#defining main function def main(): A = [] # List which ill have all numbers happy = [] # list of all happy indices x = int(input("enter number of values in the array")) # taking number of values in the list for i in range(x): # a for loop for taking aall the inputs y = int(input("enter a value")) A. append(y) maximum = A[0] # initializing maximum variable to A[O] which is the first value. this means #A[1] in our program where our indexing starts from 1 happy.append(1) # because there is no element before 1st number for i in range(1,x): # checking if each index is a happy index if A[i] > maximum: # checking the condition happy.append(i+1) # if greater than append it maximum = A[i] # set the new maximum else: continue # continue with other index print("The happy index are" + str(happy)) # print the result # calling the main function if __name__ == "_main__": main()

Screenshot of the result for a sample array :

enter number of values in the array10 enter a value9 enter a value2 enter a value4 lenter a value10 enter a value21 enter a value112 enter a value23 enter a value212 enter a value89 enter a value1100 The happy index are[1, 4, 5, 6, 8, 10] Press any key to continue ...

Running time for the algorithm : O(n)

Correctness of our algorithm :

In the second for loop used to check whether the index is correct we are comparing it with the maximum upto j-1.So if jth index value is greater than this maximum then it definitely means that it is greater than all the values before it.By definition it is a happy index and we update the maximum for the next case.So all the values that we are appending in the list will be happy values.

Pre condition : N > 0 i.e we will be provided with atleast one number and A[i] != A[j] for all i and j in range 1 to n both inclusive and i!=j.

Post condition : happy list is of all index which are happy

Program terminates as we check for at maximum n elements.

Loop variant (second loop) : if we are checking for jth element then maximum is the maximum of elements upto j-1.

From loop invariant and the argument we did before we achieve post condition.So our program is correct.

Expanation :

We can see that we used only two for loops and this for loops are not nested they are in parllel and all other program statements take constant time.This for loop takes O(n) time.So our program running time complexity is O(n).