Perfect Peak of Array
Problem Description
Given an integer array A of size N.
You need to check that whether there exists an element which is strictly greater than all the elements on the left of it and strictly smaller than all the elements on the right of it.
If it exists return 1 else return 0.
NOTE:
Problem Constraints
3 <= N <= 105
1 <= A[i] <= 109
Input Format
First and only argument is an integer array A containing N integers.
Output Format
Return 1 if there exist a element that is strictly greater than all the elements on left of it and strictly smaller than all the elements on right of it else return
Example Input
Input 1:
A = [5, 1, 4, 3, 6, 8, 10, 7, 9]
Input 2:
A = [5, 1, 4, 4]
Example Output
Output 1:
1
Output 2:
0
Example Explanation
Explanation 1:
A[4] = 6 is the element we are looking for.
All elements on left of A[4] are smaller than it and all elements on right are greater.
Explanation 2:
No such element exits.
Solution
class Solution:
# @param A : list of integers
# @return an integer
def perfectPeak(self, A):
found=False
left_gre=[A[0]]*(len(A))
right_less=[A[-1]]*(len(A))
#print(left_gre)
for i in range(1,len(A)):
if A[i]>left_gre[i-1]:
left_gre[i]=A[i]
else:
left_gre[i]=left_gre[i-1]
#print(i,A[i],left_gre[i-1],left_gre[i])
for i in range(len(A)-2,-1,-1):
if right_less[i+1]>A[i]:
right_less[i]=A[i]
else:
right_less[i]=right_less[i+1]
#print(A)
#print(left_gre)
#print(right_less)
for i in range(1,len(A)-1):
if A[i]>left_gre[i-1] and A[i]<right_less[i+1]:
return 1
return 0
Solution ScreenShot:
Comments
Post a Comment