Posts tagged as “fast slow”

花花酱 LeetCode 202. Happy Number

By zxi on December 5, 2021

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Solution: Simulation

We can use a hasthable to store all the number we generated so far.

Time complexity: O(L)
Space complexity: O(L)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

unordered_set<int> s;

while (n != 1) {

if (!s.insert(n).second) return false;

n = getNext(n);

}

return true;

}

};

Optimization: Space reduction

Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.

Time complexity: O(L)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

int slow = n;

int fast = getNext(n);

do {

slow = getNext(slow);

fast = getNext(getNext(fast));

} while (slow != fast);

return slow == 1;

}

};

花花酱 LeetCode 19. Remove Nth Node From End of List

By zxi on September 19, 2018

Problem

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution 0: Cheating! store the nodes in an array

C++

// Author: Huahua

class Solution {

public:

ListNode *removeNthFromEnd(ListNode *head, int n) {

if (!head) return nullptr;

vector<ListNode *> nodes;

ListNode *cur = head;

while (cur) {

nodes.push_back(cur);

cur = cur->next;

}

if (n == nodes.size()) return head->next;

ListNode* nodes_to_remove = nodes[nodes.size()-n];

ListNode* parent = nodes[nodes.size() - n - 1];

parent->next = nodes_to_remove->next;

delete nodes_to_remove;

return head;

}

};

Solution 1: Two passes

Time complexity: O(L)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode* removeNthFromEnd(ListNode* head, int n) {

int l = 0;

ListNode* cur = head;

while (cur) {

++l;

cur = cur->next;

}

if (n == l) {

ListNode* ans = head->next;

delete head;

return ans;

}

l -= n;

cur = head;

while (--l) cur = cur->next;

ListNode* node = cur->next;

cur->next = node->next;

delete node;

return head;

}

};

Solution 2: Fast/Slow Pointers + Dummy Head / Prev

Fast pointer moves n steps first, and then slow pointer starts moving.

When fast pointer reaches tail, slow pointer is n-th node from the end.

Time complexity: O(L)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode* removeNthFromEnd(ListNode* head, int n) {

ListNode* fast = head;

for (int i = 0; i < n; ++i)

fast = fast->next;

ListNode dummy(0);

dummy.next = head;

ListNode* prev = &dummy;

while (fast) {

fast = fast->next;

prev = prev->next;

}

ListNode* node = prev->next;

prev->next = node->next;

delete node;

return dummy.next;

}

};

Java

// Author: Huahua

class Solution {

public ListNode removeNthFromEnd(ListNode head, int n) {

ListNode dummy = new ListNode(0);

dummy.next = head;

ListNode fast = head;

while (n-- > 0) fast = fast.next;

ListNode prev = dummy;

while (fast != null) {

fast = fast.next;

prev = prev.next;

}

prev.next = prev.next.next;

return dummy.next;

}

Python3

# Author: Huahua

class Solution:

def removeNthFromEnd(self, head, n):

dummy = ListNode(0)

dummy.next = head

fast, prev = head, dummy

for _ in range(n):

fast = fast.next

while fast:

fast, prev = fast.next, prev.next

prev.next = prev.next.next

return dummy.next

Posts tagged as “fast slow”

花花酱 LeetCode 202. Happy Number

Solution: Simulation

C++

Optimization: Space reduction

C++

花花酱 LeetCode 2095. Delete the Middle Node of a Linked List

Solution: Fast / Slow pointers

C++

花花酱 LeetCode 143. Reorder List

Solution: Three steps

C++

花花酱 LeetCode 19. Remove Nth Node From End of List

Problem

Solution 0: Cheating! store the nodes in an array

C++

Solution 1: Two passes

C++

Solution 2: Fast/Slow Pointers + Dummy Head / Prev

C++

Java

Python3

花花酱 LeetCode 141. Linked List Cycle

Problem

Solution1: HashTable

Solution2: Fast + Slow pointers