iamprayush

class Solution:
    def findDuplicate(self, arr: List[int]) -> int:
        # Awesome proof here: https://youtu.be/9YTjXqqJEFE?t=431
        hare, tortoise = 0, 0
        low_speed = False
        while True:
            if low_speed:
                hare = arr[hare]
            else:
                hare = arr[arr[hare]]

iamprayush

class Solution:
    def sortColors(self, arr: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Move zeros to the first non-zero ind and twos to the
        # last non-two ind.
        n = len(arr)
        start, end = 0, n - 1
        ind = 0

iamprayush

for _ in range(int(input())):
	n = int(input())
	arr = input().split()
	for i in range(n):
		arr[i] = int(arr[i])
	repeat, missing = -1, -1

	for i in range(n):
		if arr[abs(arr[i]) - 1] < 0:
			repeat = abs(arr[i])

iamprayush

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n//2):
            l, r = i, n - i - 1
            x = 0
            for j in range(l, r):

iamprayush

'''
Simplest Approach( O(1) extra space without using Insertion Sort)

Time Complexity: O(nlogn) => As we sort both the arrays at the end.
Space Complexity: O(1) => apart from I/O

Procedure/Algo
1.
Take two pointers , lets call them ptr1 and ptr2.
ptr1 runs from end of array1 till the first element. ( endIndex -> 0 )

iamprayush

class Solution:
    def without_dp_array(self, arr: List[int]) -> int:
        n = len(arr)
        best = max(arr)
        curr = 0
        for ele in arr:
            if ele > curr + ele:
                curr = ele
            else:
                curr += ele

iamprayush

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 0:
            return []
        merged_intervals = []
        intervals.sort()

        l1, r1 = intervals[0]
        for i in range(1, len(intervals)):
            l2, r2 = intervals[i]

iamprayush

def gcd_euclidean(x, y):
    if x < y:
        x, y = y, x
    if y == 0:
        return x
    return gcd_euclidean(y, x % y)

def gcd_euclidean_iter(x, y):
    if x < y:   x, y = y, x
    while y:

iamprayush

from math import factorial

def uniquePathsDP(n, m):
    dp = [[0] * m for i in range(n)]
    for i in range(n):
        dp[i][0] = 1
    for j in range(m):
        dp[0][j] = 1
    for i in range(1, n):
        for j in range(1, m):

iamprayush

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n, m = len(matrix), len(matrix[0])

        change_row_0 = 0 in matrix[0]
        change_col_0 = False
        for i in range(n):