FilesExpand file tree

main

/

is_sorted.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (42 loc) · 1.24 KB

main

/

is_sorted.py

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (42 loc) · 1.24 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

"""

Is Sorted

Check whether a stack is sorted in ascending order from bottom to top

using a single auxiliary stack.

Reference: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Complexity:

Time: O(n)

Space: O(n)

"""

from __future__ import annotations

def is_sorted(stack: list[int]) -> bool:

"""Check if a stack is sorted in ascending order (bottom to top).

Args:

stack: A list representing a stack (bottom to top).

Returns:

True if sorted in ascending order, False otherwise.

Examples:

>>> is_sorted([1, 2, 3, 4, 5, 6])

True

>>> is_sorted([6, 3, 5, 1, 2, 4])

False

>>> stack = [1, 2, 3]

>>> is_sorted(stack)

True

>>> stack # original stack is preserved on True

[1, 2, 3]

"""

storage_stack: list[int] = []

for _ in range(len(stack)):

if len(stack) == 0:

break

first_val = stack.pop()

storage_stack.append(first_val)

if len(stack) == 0:

break

second_val = stack.pop()

if first_val < second_val:

return False

stack.append(second_val)

for _ in range(len(storage_stack)):

stack.append(storage_stack.pop())

return True