Array - Michael's Blog

Rotate Image

48. Rotate Image You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? public class Solution { public void rotate(int[][] matrix) { if (matrix == null) { return; } int n = matrix.length; for (int i = 0; i

Array

Search Insert Position

35. Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,

LeetCode

Median of Two Sorted Arrays

4. Median of Two Sorted Arrays There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.

LintCode

First Position of Target

LintCode-14.First Position of Target For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1. Example If the array is [1, 2, 3, 3,

LintCode

Majority Number

LintCode-46. Majority Number Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it. Example Given [1, 1, 1, 1, 2, 2, 2], return 1 Challenge O(n) time and O(1) extra space This problem could

LintCode

Subarray Sum

LintCode-138.Subarray Sum Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number. Notice: There is at least one subarray that it's sum equals to zero. Have you met

LintCode

The Smallest Difference

LintCode-387.The Smallest Difference Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which is B[j], so that the difference

LintCode

Interleaving Positive and Negative Numbers

LintCode-144.Interleaving Positive and Negative Numbers Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers. Notice: You are not necessary to keep the original order of positive integers or negative integers. Example: Given [-1, -2, -3, 4, 5, 6], after re-range, it

LintCode

Maximum Subarray Difference

LintCode-45.Maximum Subarray Difference Given an array with integers. Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest. Return the largest difference. Notice: The subarray should contain at least one number Example: For [1, 2, -3, 1], return 6. Challenge: O(n) time

LintCode

Maximum Subarray II

LintCode-42.Maximum Subarray II Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum. Notice: The subarray should contain at least one number Example: For given [1, 3, -1, 2, -1, 2], the two

LintCode

Best Time to Buy and Sell Stock III

LintCode-151.Best Time to Buy and Sell Stock III Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Notice: You may not engage in

LintCode

Partition Array by Odd and Even

LintCode-373.Partition Array by Odd and Even Partition an integers array into odd number first and even number second. Example: Given [1, 2, 3, 4], return [1, 3, 2, 4] Challenge: Do it in-place. public class Solution { /** * @param nums: an array of integers * @return: nothing */ public void partitionArray(int[] nums)

LintCode

Trapping Rain Water

LintCode-363.Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. Example: Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. Challenge: O(n)

LintCode

Two Sum Closest

LintCode-533.Two Sum Closest Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target. Return the difference between the sum of the two integers and the target. Example: Given array nums = [-1, 2, 1, -4], and target

LintCode

Maximum Subarray

LintCode-41.Maximum Subarray Given an array of integers, find a contiguous subarray which has the largest sum. Notice: The subarray should contain at least one number. Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.