7 posts tagged with "Two Pointers"

class Solution1:
    def rotate(self, nums: list[int], k: int) -> None:
        if len(nums) > 1:
            k %= len(nums)
            nums[:-k], nums[-k:] = nums[-k:], nums[:-k]


class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        def reverse(start, stop):
            for i in range((stop - start) // 2):
                l, r = start + i, stop - 1 - i
                nums[l], nums[r] = nums[r], nums[l]

        k %= len(nums)
        reverse(0, len(nums) - k)
        reverse(len(nums) - k, len(nums))
        reverse(0, len(nums))

class Solution:
    def maxArea(self, height: list[int]) -> int:
        result = 0
        l, r = 0, len(height) - 1
        while l != r:
            result = max(result, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return result

class Solution:
    def threeSum(self, nums: list[int]):
        result = set()
        zero, neg, pos = counters = {}, {}, {}
        for num in nums:
            counter = counters[(num > 0) + (num != 0)]
            counter[num] = counter.get(num, 0) + 1
        # 0,0,0
        if zero.get(0, 0) >= 3:
            result.add((0, 0, 0))
        # -,+,?
        for n in neg:
            for p in pos:
                target: int = -(n + p)
                counter = counters[(target > 0) + (target != 0)]
                if target in counter:
                    triplet = tuple(sorted([n, p, target]))
                    if target in (n, p):  # duplicate
                        if counter[target] >= 2:
                            result.add(triplet)
                    else:
                        result.add(triplet)
        return result

class Solution:
    def mergeAlternately(self, w1: str, w2: str) -> str:
        L1, L2 = len(w1), len(w2)
        result = []
        for i in range(max(L1, L2)):
            if i < L1:
                result.append(w1[i])
            if i < L2:
                result.append(w2[i])
        return ''.join(result)

from typing import Optional


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


class Solution1:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        l = r = d = ListNode(next=head)
        for _ in range(n - 1):
            r = r.next
        while r.next and r.next.next is not None:
            l, r = l.next, r.next
        l.next = l.next.next
        return d.next


class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        l = r = head
        for _ in range(n):
            r = r.next
        if r is None:
            return head.next
        while r.next:
            l, r = l.next, r.next
        l.next = l.next.next
        return head

class Solution:
    def isHappy(self, n: int) -> bool:
        visiteds = set()
        while n not in visiteds:
            if n == 1:
                return True
            visiteds.add(n)
            n = sum(int(x) ** 2 for x in str(n))
        return False

class Solution1:
    def backspaceCompare(self, s: str, t: str) -> bool:
        S = '#'
        ss, st = [], []
        for c in s:
            if c != S:
                ss.append(c)
            elif ss:
                ss.pop()
        for c in t:
            if c != S:
                st.append(c)
            elif st:
                st.pop()
        return ss == st


class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def go_left(string, pointer, backspace):
            S = '#'
            while pointer >= 0 and (backspace or string[pointer] == S):
                backspace += (-1) ** (string[pointer] != S)
                pointer -= 1
            return pointer, backspace

        ps, pt = len(s) - 1, len(t) - 1  # pointer
        bs, bt = 0, 0  # backspace
        while True:
            (ps, bs), (pt, bt) = go_left(s, ps, bs), go_left(t, pt, bt)
            if not (ps >= 0 and pt >= 0 and s[ps] == t[pt]):
                return ps == pt == -1
            ps -= 1
            pt -= 1