LC 406 & LC 419 & LC 667 & LC 908

Solution to LeetCode 406 Queue Reconstruction by Height, LeetCode 419 Battleships in a Board, LeetCode 667 Beautiful Arrangement II, and LeetCode 908 Smallest Range I.

LeetCode 406

Queue Reconstruction by Height (Medium) [link]

Idea: Sort and insert. Time complexity O(n).

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (-x[0], x[1]))
        res=[]
        for i in people:
            if i[1] >= len(res):
                res.append(i)
            elif i[1] < len(res):
                res.insert(i[1],i)
        return res

LeetCode 419

Battleships in a Board (Medium) [link]

Calculate the number of left-up points of battleships. The left-up points of battleships satisfy: 1)board[i][j]='X' 2)board[i][j-1]='.' 3) board[i-1][j]='.'.

Time complexity O(mn). Space complexity O(1).

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        cnt = 0
        for i, row in enumerate(board):
            for j, ch in enumerate(row):
                if ch == "X" and not ((i > 0 and board[i-1][j] == 'X') or (j > 0 and board[i][j-1] == 'X')) :
                    cnt += 1
        return cnt

LeetCode 667

Beautiful Arrangement II (Medium) [link]

For all k+1 numbers from index n-k-2 to index n-1 , the absolute differences between them are different. Time complexity O(n). Space complexity O(1).

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        res = list(range(1, n-k)) # from 1 to n-k-1
        i = n-k # from n-k to n, there are k+1 numbers
        j = n
        while i <= j:
            res.append(i)
            if i != j:
                res.append(j)
            i += 1
            j -= 1
        return res

LeetCode 908

Smallest Range I (Easy) [link]

For any nums[i], the range of varying is [nums[i]-k, nums[i]+k]. If the previous max difference is d=max-min, and d<=2*k, the answer is 0, otherwise the answer is d-2*k.

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        MAX = nums[0]
        MIN = nums[0]
        for i in nums:
            if i >= MAX:
                MAX = i
            if i <= MIN:
                MIN = i
        return max(0,MAX-MIN-2*k)