Array

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules. ...

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] Example 3: Input: matrix = [[1]] Output: [[1]] Example 4: Input: matrix = [[1,2],[3,4]] Output: [[3,1],[4,2]] Constraints: ...

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order. Example 1: Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]] Example 2: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Constraints: 1 <= nums.length <= 8 -10 <= nums[i] <= 10 Solution class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); permuteAt(0, nums, res); return res; } void permuteAt(int i, int[] nums, List<List<Integer>> res) { if (i == nums.length) { res.add(toList(nums)); return; } Set<Integer> seen = new HashSet<>(); for (int j = i; j < nums.length; j++) { if (seen.add(nums[j])) { swap(i, j, nums); permuteAt(i + 1, nums, res); swap(i, j, nums); } } } void swap(int i, int j, int[] arr) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } List<Integer> toList(int[] values) { List<Integer> res = new ArrayList<>(values.length); for (int val : values) { res.add(val); } return res; } }

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3]. ...

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n. ...

Given two sparse vectors, compute their dot product. Implement class SparseVector: SparseVector(nums) Initializes the object with the vector nums dotProduct(vec) Compute the dot product between the instance of SparseVector and vec A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector. Follow up: What if only one of the vectors is sparse? ...

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. Implement the MovingAverage class: MovingAverage(int size) Initializes the object with the size of the window size. double next(int val) Returns the moving average of the last size values of the stream. Example 1: Input ["MovingAverage", "next", "next", "next", "next"] [[3], [1], [10], [3], [5]] Output [null, 1.0, 5.5, 4.66667, 6.0] Explanation MovingAverage movingAverage = new MovingAverage(3); movingAverage.next(1); // return 1.0 = 1 / 1 movingAverage.next(10); // return 5.5 = (1 + 10) / 2 movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3 movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3 Constraints: ...

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. ...

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Note: You must not use any built-in BigInteger library or convert the inputs to integer directly. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Constraints: 1 <= num1.length, num2.length <= 200 num1 and num2 consist of digits only. Both num1 and num2 do not contain any leading zero, except the number 0 itself. Solution class Solution { public String multiply(String num1, String num2) { int[] products = new int[num1.length() + num2.length()]; for (int i = 0; i < num1.length(); i++) { for (int j = 0; j < num2.length(); j++) { int d1 = num1.charAt(i) - '0'; int d2 = num2.charAt(j) - '0'; products[i + j + 1] += d1 * d2; } } int carry = 0; for (int i = products.length - 1; i >= 0; i--) { int tmp = (products[i] + carry) % 10; carry = (products[i] + carry) / 10; products[i] = tmp; } StringBuilder sb = new StringBuilder(); for (int product: products) { if (product == 0 && sb.length() == 0) { continue; } sb.append(product); } if (sb.length() == 0) { sb.append("0"); } return sb.toString(); } }

Pair Sums Given a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k. If an integer appears in the list multiple times, each copy is considered to be different; that is, two pairs are considered different if one pair includes at least one array index which the other doesn’t, even if they include the same values. Signature int numberOfWays(int[] arr, int k) Input n is in the range [1, 100,000]. Each value arr[i] is in the range [1, 1,000,000,000]. k is in the range [1, 1,000,000,000]. Output Return the number of different pairs of elements which sum to k. ...