Two pointers Flashcards

(5 cards)

1
Q

What is the Two Pointers pattern and when is it used?

A

Uses two pointers to traverse array/list for efficient solutions.

Use Case: Sorted arrays, linked lists, pair-wise comparisons.

Example: [Merge Two Sorted Lists]. Action: Verbalize use case aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the key steps in the Two Pointers technique?

A
  1. Initialize pointers (e.g., left=0, right=n-1).
  2. Move based on condition (e.g., sum < target).
  3. Update result (e.g., store pair).

Action: Explain steps for [Merge Two Sorted Lists] aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How does the Two Pointers technique apply to [Merge Two Sorted Lists]?

A

Merge two sorted linked lists by comparing nodes, attaching the smaller to the result, and advancing the pointer.

Action: Verbalize solution logic aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the complexity and gotchas of the Two Pointers technique?

A

Time complexity: O(n+m), Space complexity: O(1).

Gotchas: Empty lists, one list longer.

Action: List edge cases for [Merge Two Sorted Lists] aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Code example for the Two Pointers technique.

A

```python
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: ‘ListNode’ = None):
self.val = val
self.next = next
def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
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
current.next = list1 or list2
return dummy.next
~~~

How well did you know this?
1
Not at all
2
3
4
5
Perfectly