Lists, Stacks & Queues (Medium)Master fundamental data structures: Linked Lists, Stacks, and Queues with their implementations and common problems.

211. Implement Stack using Array

Problem Statement

Implement a basic Stack data structure using an array (or list in Python). Support the following operations: * `push(x)`: Add x to stack. * `pop()`: Remove and return top element. * `top()`: Return top element without removing. * `isEmpty()`: Return true if stack is empty. **Example:** ``` stack = MyStack() stack.push(10) stack.push(20) stack.top() -> 20 stack.pop() -> 20 stack.isEmpty() -> False ```

Approach

1. **Underlying Structure**: Use a dynamic array (Python List). 2. **Operations**: * `push`: `list.append(x)` (O(1)). * `pop`: `list.pop()` (O(1)). * `top`: `list[-1]` (O(1)). * `isEmpty`: `len(list) == 0` (O(1)).

Solution

class MyStack:
    def __init__(self):
        self.stack = []
        
    def push(self, x):
        self.stack.append(x)
        
    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
        return None
        
    def top(self):
        if not self.isEmpty():
            return self.stack[-1]
        return None
        
    def isEmpty(self):
        return len(self.stack) == 0

# Test
s = MyStack()
s.push(10)
s.push(20)
print(s.top())
print(s.pop())
print(s.isEmpty())

212. Implement Queue using Array

Problem Statement

Implement a basic Queue data structure. Support the following operations: * `enqueue(x)`: Add x to the rear. * `dequeue()`: Remove and return front element. * `front()`: Return front element. * `isEmpty()`: Return true if queue is empty. Note: Using `list.pop(0)` in Python is O(N). Can you verify the behavior or suggest a better underlying structure for a real queue? (Ideally `collections.deque`, but here let's implement with basic logic).

Approach

1. **Queue**: FIFO (First-In, First-Out). 2. **List Implementation**: * `enqueue`: `append` is O(1). * `dequeue`: `pop(0)` is O(N) because elements shift. 3. **Optimization**: For this problem, we'll demonstrate the basic list operations but acknowledge the performance cost. A real-world Python queue uses `collections.deque`.

Solution

class MyQueue:
    def __init__(self):
        self.queue = []
        
    def enqueue(self, x):
        self.queue.append(x)
        
    def dequeue(self):
        if not self.isEmpty():
            return self.queue.pop(0) # O(N) operation
        return None
        
    def front(self):
        if not self.isEmpty():
            return self.queue[0]
        return None
        
    def isEmpty(self):
        return len(self.queue) == 0

# Test
q = MyQueue()
q.enqueue(1)
q.enqueue(2)
print(q.front())
print(q.dequeue())
print(q.isEmpty())

220. Detect Cycle in Linked List

Problem Statement

Given the `head` of a linked list, determine if the linked list has a cycle in it. Return `true` if there is a cycle in the linked list. Otherwise, return `false`. **Example:** ``` 3 -> 2 -> 0 -> -4 -> (back to 2) Output: true ```

Approach

1. **Floyd's Cycle-Finding Algorithm** (Tortoise and Hare). 2. **Logic**: * Use two pointers, `slow` and `fast`. * `slow` moves 1 step, `fast` moves 2 steps. * If there is a cycle, `fast` will eventually lap `slow` and they will meet. * If `fast` reaches `None`, there is no cycle.

Solution

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head):
    if not head or not head.next:
        return False
        
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
            
    return False

221. Reverse Linked List

Problem Statement

Given the `head` of a singly linked list, reverse the list, and return *the reversed list*. **Example:** ``` Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] ```

Approach

1. **Iterative Approach**: * Maintain `prev` (initially None) and `curr` (head). * Save `curr.next` to a temp variable. * Point `curr.next` backwards to `prev`. * Move `prev` to `curr`. * Move `curr` to `temp` (next node). * Return `prev` as the new head.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head
    
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
        
    return prev

224. Merge Two Sorted Lists

Problem Statement

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists. **Example:** ``` Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4] ```

Approach

1. **Dummy Head**: Use a dummy node to simplify edge cases for the head of the result list. 2. **Logic**: * Compare heads of `l1` and `l2`. * Append the smaller one to `current.next`. * Advance `current` and the pointer of the chosen list. * If one list is exhausted, append the remainder of the other list.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    current = dummy
    
    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
        
    if list1:
        current.next = list1
    if list2:
        current.next = list2
        
    return dummy.next

215. Stock Span Problem (Monotonic Stack)

Problem Statement

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day. The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day. **Example:** ``` Input: [100, 80, 60, 70, 60, 75, 85] Output: [1, 1, 1, 2, 1, 4, 6] ```

Approach

1. **Monotonic Stack**: We need finding the *previous greater element*. 2. **Logic**: * Maintain a stack of pairs `(price, span)`. * For a new price, pop from stack while `stack.top.price <= current_price`. * Add the spans of popped elements to the current span (initially 1). * Push `(current_price, total_span)`. * Return `total_span`.

Solution

class StockSpanner:
    def __init__(self):
        self.stack = [] # (price, span)

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

# Test
# obj = StockSpanner()
# param_1 = obj.next(price)

Back

Lists, Stacks & Queues (Medium) / 211. Implement Stack using Array

00:00

1/6

211. Implement Stack using Array

Medium

Implement a basic Stack data structure using an array (or list in Python). Support the following operations:

push(x): Add x to stack.
pop(): Remove and return top element.
top(): Return top element without removing.
isEmpty(): Return true if stack is empty.

Example:

stack = MyStack()
stack.push(10)
stack.push(20)
stack.top() → 20
stack.pop() → 20
stack.isEmpty() → False

1
Underlying Structure: Use a dynamic array (Python List).
2
Operations:
3
push: list.append(x) (O(1)).
4
pop: list.pop() (O(1)).
5
top: list[-1] (O(1)).
6
isEmpty: len(list) == 0 (O(1)).

PYTHON PLAYGROUND

⏳ Loading editor…