Details:

• Given an array numbers = {2, 7, 8, 5, 1, 6, 3, 9, 4}. Check the below conditions, both the conditions should be satisfied.

• If arr[i – 1] < arr[i] > arr[i 1], where 1 < i < N – 1, then arr[i] is the peak element.

• If arr[0] > arr[1], then arr[0] is the peak element, where N is the size of the array.

• If arr[N – 2] < arr[N – 1], then arr[N – 1] is the peak element, where N is the size of the array.

• If more than one peak element exists in the array, then the minimum value among them needs to be printed.

Example:

1st Iteration - 8, 6, 9 are peak values. 
Remove the smallest ele. Remove 6. 
New arr {2, 7, 8, 5, 1, 3, 9, 4}. Output Arr - {6}

2nd Iteration - 8, 9 are peak values. 
Remove the smallest ele. Remove 8. 
New arr {2, 7, 5, 1, 3, 9, 4}. Output Arr - {6, 8}

3rd Iteration - 7, 9 are peak values. 
Remove the smallest ele. Remove 7. 
New arr {2, 5, 1, 3, 9, 4}. Output Arr - {6, 7, 8}

4th Iteration - 5, 9 are peak values. 
Remove the smallest ele. Remove 5. 
New arr {2, 1, 3, 9, 4}. Output Arr - {6, 7, 8, 5}

5th Iteration - 2, 9 are peak values. 
Remove the smallest ele. Remove 2. 
New arr {1, 3, 9, 4}. Output Arr - {6, 7, 8, 5, 2}

6th Iteration - 9 are peak values. 
Remove the smallest ele. Remove 9. 
New arr {1, 3, 4}. Output Arr - {6, 7, 8, 5, 2, 9}

7th Iteration - 4 are peak values. 
Remove the smallest ele. Remove 4. 
New arr {1, 3}. Output Arr - {6, 7, 8, 5, 2, 9, 4}

8th Iteration - 3 are peak values. 
Remove the smallest ele. Remove 3. 
New arr {1}. Output Arr - {6, 7, 8, 5, 2, 9, 4, 3}

9th Iteration - 1 are peak values. 
Remove the smallest ele. Remove 1. 
New arr {1}. Output Arr - {6, 7, 8, 5, 2, 9, 4, 3, 1}

Output: {6, 8, 7, 5, 2, 9, 4, 3, 1}

My Code:

nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]

def deleteMinimalPeaks(nums):
    from queue import PriorityQueue as pq
    
    if len(nums) <= 1:
        return nums
    
    peakq = pq()
    out = []
    n = len(nums)
    
    ridx = [i 1 for i in range(n)]
    lidx = [i-1 for i in range(n)]
    
    nums.append(-1)
    
    if nums[0] > nums[1]:
        peakq.put((nums[0], 0))
        
    if nums[n-1] > nums[n-2]:
        peakq.put((nums[n-1], n-1))
        
    for i in range(1, n-1):
        if nums[i] > nums[i-1] and nums[i] > nums[i 1]:
            peakq.put((nums[i], i))
            
    if peakq.empty():
        nums.pop()
        return nums[::-1]
    
    while(not peakq.empty()):
        val, idx = peakq.get()
        out.append(val)
        
        if len(out) == len(nums):
            break
        
        if ridx[idx] <= n-1:
            lidx[ridx[idx]] = lidx[idx]
            
        if lidx[idx] >= 0:
            ridx[lidx[idx]] = ridx[idx]
            
        if ridx[idx] <= n-1 \
        and nums[ridx[idx]] > nums[ridx[ridx[idx]]] \
        and nums[ridx[idx]] > nums[lidx[ridx[idx]]]:
            peakq.put( (nums[ridx[idx]], ridx[idx]) )
            
        if lidx[idx] >= 0 \
        and nums[lidx[idx]] > nums[lidx[lidx[idx]]] \
        and nums[lidx[idx]] > nums[ridx[lidx[idx]]]:
            peakq.put( (nums[lidx[idx]], lidx[idx]) )
        
    return out

deleteMinimalPeaks(nums)

Question:

The code is giving the correct result.

However, is there a more pythonic way to write the innermost while loop?

CodePudding user response：

I would probably use itertools to help navigate the results. Using the recipe for triplewise with some slight adaptations, we can easily iterate over multiple values in the list.

The adaptation we will make is adding buffer to the start and end of the data. This will allow us to detect if we're on the edge of the data or not.

from itertools import pairwise

def triplewise(iterable):
    for (a, _), (b, c) in pairwise(pairwise([None, *iterable, None])):
        yield a, b, c


nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]
for a, b, c in triplewise(nums):
    print(a, b, c)

None 2 7
2 7 8
...
3 9 4
9 4 None

To create a method which returns just the peaks, all you have to do is examine the middle number against its edges. We know values of None are edges.

def find_peeks(iterable):
    for a, b, c in triplewise(iterable):
        if (a is None or b > a) and (c is None or b > c):
            yield b


nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]
print(list(find_peeks(nums)))

[8, 6, 9]

To make this iterative, you could have the find_peeks method also return the index of the peek. Then you can use min to find the minimum element to remove and continue:

def find_peeks(iterable):
    for i, (a, b, c) in enumerate(triplewise(iterable)):
        if (a is None or b > a) and (c is None or b > c):
            yield b, i


def iterative_peeks(iterable):
    while iterable:
        peek, index = min(find_peeks(iterable))
        yield peek
        del iterable[index]


nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]
print(list(iterative_peeks(nums)))

[6, 8, 7, 5, 2, 9, 4, 3, 1]