Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

 

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Solution

class Solution {

public void moveZeroes(int[] nums) {

int nonZeroIndex = 0;

// move non zero numbers

for(int i=0; i<nums.length; i++) {

if(nums[i] != 0) {

nums[nonZeroIndex++] = nums[i];

}

}

// append 0s

for(int j=nonZeroIndex; j < nums.length; j++) {

nums[j] = 0;

}

}

}

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Solution

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

*/

class Solution {

public ListNode reverseList(ListNode head) {

ListNode prev = null;

ListNode current = head;

while(current!=null) {

ListNode next = current.next;

current.next = prev;

prev = current;

current = next;

}

return prev;

}

}

Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

Solution

class Solution {

public int findMin(int[] nums) {

// If the list has just one element then return that element.

if (nums.length == 1) {

return nums[0];

}

// initializing left and right pointers.

int left = 0, right = nums.length - 1;

// if the last element is greater than the first element then there is no

// rotation.

// e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.

// Hence the smallest element is first element. A[0]

if (nums[right] > nums[0]) {

return nums[0];

}

// Binary search way

while (right >= left) {

// Find the mid element

int mid = left + (right - left) / 2;

// if the mid element is greater than its next element then mid+1 element is the

// smallest

// This point would be the point of change. From higher to lower value.

if (nums[mid] > nums[mid + 1]) {

return nums[mid + 1];

}

// if the mid element is lesser than its previous element then mid element is

// the smallest

if (nums[mid - 1] > nums[mid]) {

return nums[mid];

}

// if the mid elements value is greater than the 0th element this means

// the least value is still somewhere to the right as we are still dealing with

// elements

// greater than nums[0]

if (nums[mid] > nums[0]) {

left = mid + 1;

} else {

// if nums[0] is greater than the mid value then this means the smallest value

// is somewhere to

// the left

right = mid - 1;

}

}

return Integer.MAX_VALUE;

}

}

Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Solution

class Solution {

public int maxProfit(int[] prices) {

int max = 0;

int start = prices[0];

int len = prices.length;

for(int i = 1;i<len; i++){

if(start < prices[i]) {

max += prices[i] - start;

}

start = prices[i];

}

return max;

}

}

Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Solution

class Solution {

public List<List<Integer>> generate(int numRows) {

List<List<Integer>> triangle = new ArrayList<List<Integer>>();

// Base case; first row is always [1].

triangle.add(new ArrayList<>());

triangle.get(0).add(1);

for (int rowNum = 1; rowNum < numRows; rowNum++) {

List<Integer> row = new ArrayList<>();

List<Integer> prevRow = triangle.get(rowNum - 1);

// The first row element is always 1.

row.add(1);

// Each triangle element (other than the first and last of each row)

// is equal to the sum of the elements above-and-to-the-left and

// above-and-to-the-right.

for (int j = 1; j < rowNum; j++) {

row.add(prevRow.get(j - 1) + prevRow.get(j));

}

// The last row element is always 1.

row.add(1);

triangle.add(row);

}

return triangle;

}

}