Category Archives: Array

Best Time to Buy and Sell Stock

By | | , ,
Leave a comment

How to get maximum profit by buying and selling a stock when at most one transaction is allowed?

In this problem, we have given an array of stock prices, the ith element represents the stock price on ith day.

If we are allowed to complete at most one transaction (i.e.,buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one. If it’s not possible to achieve any profit return 0.

For example –

Example 1-

Input – { 9, 1, 6, 3, 7, 4}

Output – 6 (Buy on day 2 (1) and sell on day 5 (7))

Example 2-

Input – {5, 4, 3, 2, 1}

Output – 0 (It is not possible to do any transaction)

→

Plus One | Add One to Number Represented as Array

By | | , ,
Leave a comment

In this problem, We have given a non-empty array which represents a non-negative integer. Write a code to add one to the number.

Each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1 –

Input:  [1, 3, 4]

Output: [1, 3, 5]

In this example, the array represents the number 134. When we add 1 to it, the new number is 135.

Example 2 –

Input : [1, 2, 9]

Output: [1, 3, 0]

The number is 129. When we add 1 to 129. The new number is 130.

Example 3 –

Input : [9, 9, 9]

Output: [1, 0, 0, 0]

For the number 999, when you add 1, the new number would be 1000. If you think in terms of array, the new array size would be the previous array size plus one.

→

Majority Element II | N/3 Repeated Number

By | | , ,
Leave a comment

In this tutorial, I am going to discuss a very interesting problem find N/3 repeated number in an array.

Given an array of size n, Write a code to find all the elements that appear more than n/3 times.

NOTE: We have to solve this problem in linear time and in O(1) space.

Example 1:

Input : [3, 2, 3]

Output: 3

In this example, The size of this array is 3. We have to find all the numbers which occurred more than n/3 where n is the size of the array. The number 3 appears more than 1 times.

Example 2:

Input: [1, 1, 1, 3, 3, 2, 2, 2]

Output:[1, 2]

→