Two Pointers in 7 minutes | LeetCode Pattern

00:07:20
https://www.youtube.com/watch?v=QzZ7nmouLTI

Summary

TLDRCette vidéo présente le modèle des deux pointeurs, une technique efficace pour résoudre divers problèmes de codage, souvent rencontrée lors des entretiens techniques. Elle explique comment utiliser deux pointeurs pour optimiser des problèmes liés aux tableaux et aux chaînes, en passant d'une complexité de O(n²) à O(n). L'animateur présente trois stratégies communes : les pointeurs convergents pour comparer des éléments aux extrémités, les pointeurs parallèles pour explorer des données de manière complémentaire, et les pointeurs basés sur un critère spécifique pour naviguer dans des structures comme les listes chaînées. Des exemples concrets de problèmes LeetCode illustrent cette méthode, fournissant ainsi une base pratique pour les développeurs souhaitant accroître leur efficacité en matière de résolution de problèmes.

Takeaways

  • 🔍 Comprendre le modèle des deux pointeurs pour optimiser les algorithmes.
  • 🧩 Appliquer la technique à des problèmes comme "Move Zeros".
  • 💧 Résoudre des problèmes de conteneurs d'eau avec des pointeurs.
  • 📊 Réduire la complexité temporelle de O(n²) à O(n).
  • ✅ Identifier les problèmes adaptés à l'utilisation de deux pointeurs.
  • 💡 Pratiquer avec des exercices sur des plateformes comme LeetCode.

Timeline

  • 00:00:00 - 00:07:20

    Le pattern à deux pointeurs est une méthode puissante pour résoudre des problèmes, notamment dans les interviews de codage. En utilisant deux pointeurs qui se déplacent l'un vers l'autre ou dans la même direction, nous pouvons souvent réduire la complexité temporelle de O(n²) à O(n). Cette vidéo explore ce pattern, les types de deux pointeurs et des exemples pratiques. Les pointeurs représentent une position dans une structure de données, permettant ainsi des comparaisons efficaces sans boucles imbriquées. Nous examinons trois stratégies principales : les pointeurs convergents pour comparer les éléments aux extrémités, les pointeurs parallèles pour un suivi simultané, et les pointeurs basés sur des conditions pour des recherches spécifiques. Le pattern est généralement utilisé avec des structures de données linéaires comme les tableaux, les chaînes de caractères ou les listes chaînées. Les problèmes avec des motifs prévisibles ou demandant des paires de valeurs sont de bons candidats pour cette approche.

Mind Map

Video Q&A

  • Qu'est-ce que le modèle des deux pointeurs ?

    C'est une technique de résolution de problèmes qui utilise deux variables pour parcourir une structure de données efficacement.

  • Quand utiliser cette approche ?

    Elle est utile pour traiter des tableaux, des chaînes ou des listes chaînées, surtout lorsque les données suivent un modèle prévisible.

  • Quels sont les types de techniques de deux pointeurs ?

    Il y a trois techniques principales : les pointeurs convergents, les pointeurs parallèles, et les pointeurs basés sur des conditions.

  • Comment résoudre le problème "Move Zeros" avec cette technique ?

    Utilisez un pointeur gauche pour suivre l'emplacement des non-zéros et un pointeur droit pour parcourir le tableau.

  • Quel est l'objectif du problème "Container With Most Water" ?

    Trouver deux lignes qui peuvent emprisonner le plus d'eau entre elles.

View more video summaries

Get instant access to free YouTube video summaries powered by AI!
Subtitles
en
Auto Scroll:
  • 00:00:00
    two pointers a powerful problem solving
  • 00:00:02
    pattern where you initialize two
  • 00:00:03
    variables and move them towards each
  • 00:00:04
    other away from each other or in the
  • 00:00:06
    same direction based on the problem
  • 00:00:08
    there are currently 210 lead code
  • 00:00:10
    problems tagged with this approach which
  • 00:00:12
    so just how important it is for coding
  • 00:00:13
    interviews using this approach you can
  • 00:00:15
    reduce the time complexity of many array
  • 00:00:17
    and isting related problems from order
  • 00:00:19
    of n Square to order of n in this video
  • 00:00:21
    I will break down what the two pointers
  • 00:00:23
    pattern is types of two pointers when to
  • 00:00:26
    use it and I will walk you through
  • 00:00:27
    multiple lead code problems to help you
  • 00:00:29
    understand it better I also share a
  • 00:00:30
    resource where you can practice more
  • 00:00:32
    problems using this pattern so let's
  • 00:00:33
    jump in What is the two- pointers
  • 00:00:35
    pattern let's first understand what a
  • 00:00:37
    pointer is a pointer is simply a
  • 00:00:38
    variable that represents an index or
  • 00:00:40
    position within a data structure such as
  • 00:00:42
    an array or link list using pointers at
  • 00:00:44
    different positions we can efficiently
  • 00:00:46
    compare elements and make decisions
  • 00:00:48
    without relying on Ned Loops which would
  • 00:00:49
    otherwise lead to order of any Square
  • 00:00:51
    time complexity the twoo test technique
  • 00:00:53
    can be applied in different ways
  • 00:00:54
    depending on the problem let's explore
  • 00:00:56
    the three most common strategies first
  • 00:00:58
    converging pointers in this approach
  • 00:01:00
    pointers is start at opposite ends of a
  • 00:01:01
    data structure and move inward toward
  • 00:01:03
    each other the pointers adjust their
  • 00:01:05
    positions based on comparisons until a
  • 00:01:07
    certain condition is met or they cross
  • 00:01:09
    each other this strategy is ideal for
  • 00:01:11
    problems where we need to compare
  • 00:01:12
    elements from opposite ends of an array
  • 00:01:14
    or a string for example checking if a
  • 00:01:16
    string is a palindrome a palindrome is a
  • 00:01:18
    word phrase or sequence that reads the
  • 00:01:20
    same forward and backward to check if a
  • 00:01:22
    string is a palindrome we slice two
  • 00:01:23
    pointers one at the beginning and one at
  • 00:01:25
    the end compare characters at both the
  • 00:01:27
    pointers if they match move both
  • 00:01:29
    pointers inward if they don't match
  • 00:01:30
    return Falls repeat until the pointers
  • 00:01:32
    meet next parallel pointers in this
  • 00:01:35
    approach both pointers start at the same
  • 00:01:36
    end usually the beginning and move in
  • 00:01:38
    the same direction these pointers
  • 00:01:40
    generally serve two different but
  • 00:01:41
    complimentary roles the right pointer is
  • 00:01:43
    used to explore or find new information
  • 00:01:45
    and the left pointer is used to track
  • 00:01:47
    progress or maintain constraints sliding
  • 00:01:49
    window technique is a popular variation
  • 00:01:50
    of this approach in sliding window two
  • 00:01:53
    pointers slide across an array or string
  • 00:01:54
    while maintaining a dynamic range is
  • 00:01:56
    commonly used to find sub arrays or sub
  • 00:01:57
    strings that meet a specific criteria I
  • 00:02:00
    cover sliding window in a separate video
  • 00:02:02
    feel free to check it out if you want
  • 00:02:03
    and the last trigger based pointers in
  • 00:02:05
    this approach we move the first pointer
  • 00:02:07
    independently until it finds an element
  • 00:02:09
    that meets a certain condition after
  • 00:02:11
    this we start traversing with the second
  • 00:02:13
    pointer to find additional information
  • 00:02:15
    related to what the P pointer found this
  • 00:02:17
    technique is particularly useful when we
  • 00:02:19
    need to process elements in each stages
  • 00:02:20
    a good example of this approach is
  • 00:02:22
    finding the nth node from the end of a
  • 00:02:24
    link list we move the first pointer and
  • 00:02:26
    steps forward once the first pointer
  • 00:02:27
    reaches the nth node initialize the
  • 00:02:29
    second pointer at the head move both
  • 00:02:31
    pointers one step at a time until the
  • 00:02:33
    first pointer reaches the end at this
  • 00:02:35
    point the second pointer will be at the
  • 00:02:36
    nth node from the end when to use the
  • 00:02:38
    two-pointers pattern the two-pointer
  • 00:02:40
    algorithm is generally applied to linear
  • 00:02:41
    data structures such as arrays strings
  • 00:02:43
    or link list a strong clue that a
  • 00:02:45
    problem can be solved using the two
  • 00:02:46
    pointers technique is if the input data
  • 00:02:48
    follows a predictable pattern such as
  • 00:02:50
    salted array or palindromic string for
  • 00:02:52
    example in a salted array moving a
  • 00:02:54
    pointer to the right ensures you're
  • 00:02:55
    always moving to a greater or equal
  • 00:02:57
    value making it easy to compare the
  • 00:02:59
    values at both both the pointers another
  • 00:03:01
    strong indicator that a problem can be
  • 00:03:02
    solved using two pointers is when it
  • 00:03:04
    explicitly asks for a pair of values
  • 00:03:06
    that satisfy a condition or a result
  • 00:03:08
    that can be generated from two values
  • 00:03:10
    now let's walk through a few lead quote
  • 00:03:11
    problems to understand the two pointers
  • 00:03:13
    pattern in action if at any point you
  • 00:03:15
    feel like pausing the video and trying
  • 00:03:16
    out the problem yourself feel free to do
  • 00:03:18
    so the first problem is lead code 283
  • 00:03:20
    move zeros you are given an integer
  • 00:03:22
    array move all zeros to the end of it
  • 00:03:24
    you must do this in place without extra
  • 00:03:26
    space and maintain the relative order of
  • 00:03:28
    non-zero elements for this input the
  • 00:03:30
    output would be a I approach would be to
  • 00:03:32
    create a new temporary array initialized
  • 00:03:33
    with zeros then it read through the
  • 00:03:35
    original array and copy all nonzero
  • 00:03:37
    elements to the new array and finally
  • 00:03:39
    copy the temporary array to the original
  • 00:03:41
    array this works but it takes extra
  • 00:03:43
    space equal to the size of the input
  • 00:03:44
    array this violates one of the
  • 00:03:45
    requirements since we have to do it in
  • 00:03:47
    place if instead of focusing on moving
  • 00:03:49
    zeros you can move all non-zero elements
  • 00:03:51
    to the left the zeros will naturally
  • 00:03:52
    shift to the right therefore we only
  • 00:03:54
    need to focus on non-zero elements we
  • 00:03:56
    can use the two pointers approach to
  • 00:03:57
    solve this a right pointer is the array
  • 00:04:00
    to find non-zero elements and the left
  • 00:04:02
    pointer tracks where the next non-zero
  • 00:04:03
    element should be placed when the right
  • 00:04:05
    pointer finds a non-zero element we swp
  • 00:04:07
    it with the element at the left pointer
  • 00:04:08
    and move both pointers forward once the
  • 00:04:10
    right pointer reaches the end all zeros
  • 00:04:12
    will end up at the right end of the
  • 00:04:14
    array as intended and all nonzero
  • 00:04:16
    elements will remain in order here is
  • 00:04:17
    how it looks like in code here I'm using
  • 00:04:19
    Java but you can find the code for other
  • 00:04:21
    popular programming languages in my
  • 00:04:22
    GitHub repository called awesome lead
  • 00:04:23
    code resources you can find the link in
  • 00:04:25
    the description start by initializing
  • 00:04:27
    the left pointer to zero it will be used
  • 00:04:28
    to track and play Place non-zero
  • 00:04:30
    elements rrate over the array using a
  • 00:04:32
    right pointer to locate non-zero
  • 00:04:33
    elements if you find a non-zero element
  • 00:04:35
    swap the element at left and right
  • 00:04:37
    pointer and increment the left pointer
  • 00:04:39
    the time complexity of this approach is
  • 00:04:40
    order of n since we trade to the AR only
  • 00:04:42
    once the space complexity is order of
  • 00:04:44
    one since we are not using any extra
  • 00:04:46
    space let's move on to our next problem
  • 00:04:48
    lead Code 11 container with most water
  • 00:04:50
    you given an array where each element
  • 00:04:52
    represents the height of a vertical line
  • 00:04:54
    the goal is to find two lines that can
  • 00:04:56
    trap the most water between them in
  • 00:04:58
    other words we are looking for the two
  • 00:04:59
    lines that form the container with the
  • 00:05:01
    maximum area the area of water trapped
  • 00:05:03
    between the two lines depends on two
  • 00:05:05
    factors the height of the Suter line
  • 00:05:06
    since filling water over the solter line
  • 00:05:08
    would result in overflow and the
  • 00:05:10
    distance between the two lines we can
  • 00:05:11
    calculate the area using the formula
  • 00:05:13
    mean of height at left and height at
  • 00:05:15
    right T right minus left where right
  • 00:05:17
    minus left represents the width of the
  • 00:05:18
    container a Brute Force approach to
  • 00:05:20
    solve this involves comparing the area
  • 00:05:22
    formed by every possible pair of lines
  • 00:05:23
    using Ned for loops and returning the
  • 00:05:25
    largest area found while this works it
  • 00:05:27
    has a Time complexity of order of any
  • 00:05:29
    Square which becomes too slow for large
  • 00:05:30
    inputs we can optimize this using the
  • 00:05:32
    two pointer approach which eliminates
  • 00:05:34
    the need to compare every pair here is
  • 00:05:36
    the idea instead of checking every pair
  • 00:05:38
    we start with the widest possible
  • 00:05:39
    container and gradually reduce the width
  • 00:05:41
    by moving the pointers inward to find if
  • 00:05:43
    a larger Ria can be formed we start by
  • 00:05:45
    placing one pointer at the beginning and
  • 00:05:47
    the other at the end of the array since
  • 00:05:48
    the container with the maximum width
  • 00:05:50
    starts at index zero and ends at index n
  • 00:05:52
    minus one intialize a Max area variable
  • 00:05:54
    to zero to keep track of the largest
  • 00:05:56
    area found so far it rate while left is
  • 00:05:58
    less than or equal to right calculate
  • 00:06:00
    the current area using the two lines
  • 00:06:01
    pointed to by left and right using the
  • 00:06:03
    formula me at height at left and height
  • 00:06:05
    at right time right minus left update
  • 00:06:07
    the max area if the current area is
  • 00:06:09
    greater move the pointer that points to
  • 00:06:10
    the soter line inward Why move the
  • 00:06:12
    pointer at the Salter line because
  • 00:06:14
    moving either pointer inward reduces the
  • 00:06:16
    BD but the shter line limits the
  • 00:06:17
    container height moving the pointer as
  • 00:06:19
    shter line inward is the only way to
  • 00:06:21
    potentially find a t line which might
  • 00:06:23
    increase the area repeat this process
  • 00:06:25
    until the poter meet this approach
  • 00:06:26
    reduces their complexity to order of n
  • 00:06:28
    since each element is processed at most
  • 00:06:30
    once here is how it looks like in code
  • 00:06:32
    you start by initializing left pointer
  • 00:06:33
    to zero and right pointer to the last
  • 00:06:35
    element initialize a variable Max area
  • 00:06:37
    to zero to store the maximum area found
  • 00:06:39
    while left is less than or equal to
  • 00:06:41
    right calculate the current area using
  • 00:06:42
    the formula update Max area if the
  • 00:06:44
    current area is greater move the pointer
  • 00:06:46
    pointing to the shorter line inward if
  • 00:06:48
    the left line is shorter increment left
  • 00:06:50
    else decrement right finally return the
  • 00:06:52
    max area here are some more liquod
  • 00:06:54
    problems you can practice using this
  • 00:06:56
    approach you can find these problems on
  • 00:06:57
    algomas doio simply head over to the
  • 00:07:00
    practice page search for this pattern or
  • 00:07:02
    use the filter drop down and start
  • 00:07:03
    practicing on this platform you can Mark
  • 00:07:05
    problems as complete or Star them for
  • 00:07:07
    later revision you can also find the
  • 00:07:09
    links to GitHub and YouTube solutions
  • 00:07:10
    for each problem you can check out the
  • 00:07:12
    fly quote patterns playlist here I hope
  • 00:07:14
    you found this video helpful make sure
  • 00:07:15
    to subscribe so you won't miss my future
  • 00:07:17
    videos thanks for watching and I will
  • 00:07:19
    see you in the next one
Tags
  • deux pointeurs
  • algorithmie
  • complexité temporelle
  • LeetCode
  • problèmes de codage
  • modèle de résolution
  • pointeurs convergents
  • pointeurs parallèles
  • pointeurs conditionnels
  • stratégies algorithmiques