from typing import *
def check(result, expected):
    assert result == expected, f"Got {result}, Expected {expected}"

1470. Shuffle The Array

Question

Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].

Return the array in the form [x1,y1,x2,y2,...,xn,yn].

Example 1:

Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7] Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7]. Example 2:

Input: nums = [1,2,3,4,4,3,2,1], n = 4 Output: [1,4,2,3,3,2,4,1] Example 3:

Input: nums = [1,1,2,2], n = 2 Output: [1,2,1,2]

Constraints:

1 <= n <= 500 nums.length == 2n 1 <= nums[i] <= 10^3

Answer

  1. Split into two lists x and y, starting at 0 and n
  2. Pair up each list by index, (x0,y0), (x1,y1), ... (xn,yn)
  3. Flatten list of tuple
class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        return [val for (x,y) in zip(nums[:n], nums[n:]) for val in (x,y)]
%%timeit

assert Solution().shuffle([2,5,1,3,4,7], 3) == [2,3,5,4,1,7]
assert Solution().shuffle([1,2,3,4,4,3,2,1], 4) == [1,4,2,3,3,2,4,1]
assert Solution().shuffle([1,1,2,2], 2) == [1,2,1,2]
2.47 µs ± 15.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

1732. Find the Highest Altitude

Question

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i​​​​​​ and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7] Output: 1 Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1. Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2] Output: 0 Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Constraints:

n == gain.length 1 <= n <= 100 -100 <= gain[i] <= 100

Answer

Each step is a delta. Cumulatively sum up the deltas and return the max

  • Time: O(n)
  • Mem: O(n)
class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        altitude = [0]
        for i, g in enumerate(gain):
            cumsum = altitude[i] + g
            altitude.append(cumsum)
            
        return max(altitude)
%%timeit

assert Solution().largestAltitude([-5,1,5,0,-7]) == 1
assert Solution().largestAltitude([-4,-3,-2,-1,4,3,2]) == 0
2.18 µs ± 28.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Slightly more performant:

  • Time: O(n)
  • Mem: O(1)
class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        altitude = 0
        highest_altitude = 0
        
        for i, g in enumerate(gain):
            altitude = altitude + g
            highest_altitude = max(highest_altitude, altitude)

        return highest_altitude
%%timeit

assert Solution().largestAltitude([-5,1,5,0,-7]) == 1
assert Solution().largestAltitude([-4,-3,-2,-1,4,3,2]) == 0
2.28 µs ± 15.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

1347. Minimum Number of Steps to Make Two Strings Anagram

Question

Given two equal-size strings s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s. Example 2:

Input: s = "leetcode", t = "practice" Output: 5 Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s. Example 3:

Input: s = "anagram", t = "mangaar" Output: 0 Explanation: "anagram" and "mangaar" are anagrams. Example 4:

Input: s = "xxyyzz", t = "xxyyzz" Output: 0 Example 5:

Input: s = "friend", t = "family" Output: 4

Constraints:

1 <= s.length <= 50000 s.length == t.length s and t contain lower-case English letters only.

Answer

  1. Find the number of different characters in each string. (delta)
  2. Pair up the different chars and count the number of pairs sum(delta.values()) // 2
from collections import Counter

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        c1 = Counter(s)
        c2 = Counter(t)
        
        keys = set((*c1.keys(), *c2.keys()))
        
        delta = {k: abs(c1[k] - c2[k]) for k in keys}
        return sum(delta.values()) // 2
%%timeit

assert Solution().minSteps('bab', 'aba') == 1
assert Solution().minSteps('leetcode', 'practice') == 5
assert Solution().minSteps('mangaar', 'anagram') == 0
assert Solution().minSteps('xxyyzz', 'xxyyzz') == 0
assert Solution().minSteps('friend', 'family') == 4
22.9 µs ± 168 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

767. Reorganize String

Question

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = "aab" Output: "aba" Example 2:

Input: S = "aaab" Output: "" Note:

S will consist of lowercase letters and have length in range [1, 500].

class Solution:
    def reorganizeString(self, S: str) -> str:
        pass
assert Solution().reorganizeString('aab') == 'aba'
assert Solution().reorganizeString('aaab') == ''
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-99-3a424297b254> in <module>
----> 1 assert Solution().reorganizeString('aab') == 'aba'
      2 assert Solution().reorganizeString('aaab') == ''

AssertionError: 

end