The Problem You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that, together with the x-axis, form a container such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. ...
The Problem Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Examples Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter. Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0. Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0. Constraints 3 <= nums.length <= 3000 -10⁵ <= nums[i] <= 10⁵ Brute Force Solution func threeSum(_ nums: [Int]) -> [[Int]] { var nums = nums let n = nums.count var res: Set<[Int]> = [] nums.sort() for i in 0 ..< n { for j in i + 1 ..< n { for k in j + 1 ..< n { if nums[i] + nums[j] + nums[k] == 0 { let val = [nums[i], nums[j], nums[k]] res.insert(val) } } } } return Array(res) } Explanation Let’s start with the brute force solution. According to the problem, we need to find triplet elements that, when added together, equal 0. By looking at examples, the first thing that comes to mind is to use three loops, add each of the elements, and compare the result with 0. If the result equals 0, we add the elements to the result. ...
The Problem Given a string s, return true if it is a palindrome, or false otherwise. A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Examples Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome. Constraints 1 <= s.length <= 2 * 10^5 s consists only of printable ASCII characters. Brute Force Solution func isPalindrome(_ s: String) -> Bool { var newStr = "" for c in s { if c.isLetter || c.isNumber { newStr += c.lowercased() } } return newStr == String(newStr.reversed()) } Explanation Let’s start with the brute force solution. According to the description, we need to check if the string contains only lowercase, alphanumeric characters and reads the same forward and backward. In Swift, you can check this using the built-in isLetter and isNumber properties. Based on this information, we iterate through all characters in the s string, verify that each character is a letter or number, update newStr with the current lowercased character, and compare the result with its reversed version. ...
The Problem Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time. A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. Examples Input: nums = [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] Output: 9 Constraints 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 Brute Force Solution func longestConsecutive(_ nums: [Int]) -> Int { var res = 0 let setOfNums: Set<Int> = Set(nums) for num in nums { var streak = 0 var curr = num while setOfNums.contains(curr) { streak += 1 curr += 1 } res = max(res, streak) } return res } Explanation Let’s start with the brute force solution. We need to increment each element by 1 to check if the incremented value exists in our input array. For example, if we have an array nums with [3, 2, 1, 100, 5], the longest consecutive sequence will be 3. If you look closely at the array [3, 2, 1, 100, 5], it has a sequence of 2, 1, which when incremented forms elements that already exist in the array (1 -> 2, 2 -> 3). By counting the number of increments, you can determine the longest sequence. The solution above does exactly that: ...
The problem Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation. Examples Input: nums = [1,2,3,4] Output: [24,12,8,6] Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0] Constraints 2 <= nums.length <= 10^5 -30 <= nums[i] <= 30 The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.) ...