Two Pointers

Two pointers

Versatile techinique used in problem-solving to efficiently traverse or manipulate sequential data structures, such as arrays or linked lists.

It involves maintaining two pointers that traverse the data structure in a coordinated manner, typically starting from different positions or moving in opposite directions. These pointers dynamically adjust based on specitic conditions or criteria, allowing for the efficient exploration of the data and enabling solutions with optimal time and space complexity. Whenever there is a requirement to find two data elements in an array that satisfy a certain condition, the two pointers pattern should be the first strategy to come to mind

 

The pointers can be used to iterate through the data structure in one or both directions, depending on the problem statemet.

 

배열이나 연결 목록과 같은 순차적 데이터 구조를 효율적으로 탐색하거나 조작하기 위해 문제 해결에 사용되는 다재다능한 기술. 일반적으로 서로 다른 위치에서 시작하거나 반대 방향으로 이동하는 조정된 방식으로 데이터 구조를 탐색하는 두 포인터를 유지하는 것을 포함. 특정조건이나 기준에 따라 동적으로 조정되어 데이터를 효율적으로 탐색하고 최적의 시간 및 공간 복잡도로 솔루션을 구현할 수 있음. 특정 조건을 충족하는 배열에서 두 개의 데이터 요소를 찾아야 할 때마다 두 포인터 패턴이 가장 먼저 떠오르는 전략이어야 함.

 

포인터는 문제 진술에 따라 한 방향 또는 양방향으로 데이터 구조를 반복하는데 사용할 수 있어야 함.

- Detecting a palindrome: Given a string, determine whether it is a palindrome or not.

 * Palindrome is a word, phrase, or sequence of characters that reads the same backwad as forward.

- Reversing an array Given an array of integers, revers it in place.

- Pair with given sum in a sorted array: Given a sorted array of integers, find a pair in the array that sums to a number T

 

 

Does your problem match this pattern?

If all of these conditions are fultilled:

1. Linear datat structure: The input data can be traversed in a linear fashion, such as an array, linked list, or string.

2. Process pairs: Process data elements at two different positions simultaneously.

3. Dynamic pointer movement: Both pointers move independently of each other according to certain conditons or criteria. In addition, both pointers might move along the same or two different data structures.

 

선형데이터 구조: 입력 데이터 배열, 연결 목록, 문자열과 같이 선형 방식으로 탐색 가능

쌍으로 처리: 두 개의 다른 위치에 있는 데이터 요소를 동시에 처리

동적 포인터 이동 :두 포인터는 특정 조건이나 기준에 따라 서로 독립적으로 이동. 또한 두 포인터는 동일하거나 두개의 다른 데이터 구조를 따라 이동 가능 

-> 배열이나 문자열을 효율적으로 탐색할 대 유용하지만, 특정 패턴을 생성하는 문제에는 적합하지 않음.

 

Prerequisites

Arrays

Linked lists

Hash maps

Stacks

Queues

Heaps

Trees

Graphs

-> Need to be familiar with Big-O notation for complexity analysis