Search a 2D Matrix II

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

 

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 

Output: false 

Solution

class Solution {

public boolean searchMatrix(int[][] matrix, int target) {

int row=0;

int col=matrix[0].length-1;

if(target < matrix[0][0] || target > matrix[matrix.length-1][matrix[0].length-1]) {

return false;

}

while(row<matrix.length && col>=0){

if(target < matrix[row][col]) {

col--;

}

else if(target > matrix[row][col]) {

row++;

} else {

return true;

}

}

return false;

}

}

Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

 

Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]] 

myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]] 

Solution

class MyHashMap {

int[] data;

public MyHashMap() {

data = new int[1000001];

Arrays.fill(data, -1);

}

public void put(int key, int value) {

data[key] = value;

}

public int get(int key) {

return data[key];

}

public void remove(int key) {

data[key]=-1;

}

}

/**

* Your MyHashMap object will be instantiated and called as such:

* MyHashMap obj = new MyHashMap();

* obj.put(key,value);

* int param_2 = obj.get(key);

* obj.remove(key);

*/

Maximum Product of Three Numbers

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Example 1:

Input: nums = [1,2,3]
Output: 6

Example 2:

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

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

Solution

class Solution {

public int maximumProduct(int[] nums) {

Arrays.sort(nums);

int n = nums.length;

return Math.max(nums[n-1]*nums[n-2]*nums[n-3], nums[0]*nums[1]*nums[n-1]);

}

}

String Compression

 Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

• If the group's length is 1, append the character to s.
• Otherwise, append the character followed by the group's length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

 

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Solution

class Solution {

public int compress(char[] chars) {

int index=0, indexAns=0;

while(index < chars.length) {

int count=0;

Character currentChar = chars[index];

while(index < chars.length && currentChar == chars[index]) {

count++;

index++;

}

chars[indexAns++] = currentChar;

if(count > 1) {

for(Character c : Integer.toString(count).toCharArray()) {

chars[indexAns++] = c;

}

}

}

return indexAns;

}

}

Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

 

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

Solution

class Solution {

public boolean canConstruct(String ransomNote, String magazine) {

int[] count = new int[26];

// build lookup array with the letters in magazine

for(Character c:magazine.toCharArray()){

count[c-'a']++;

}

// check ransome can be constructed by using letters from magazine

for(Character c:ransomNote.toCharArray()){

count[c-'a']--;

if(count[c-'a']<0){

return false;

}

}

return true;

}

}