DEV Community: Ajay k

Best Time to Buy and Sell Stock

Ajay k — Wed, 27 Jul 2022 18:23:23 +0000

Today lets see one of the basic array problem,

for Best Time to Buy and Sell Stock problem we need to find best day to buy (low price ) and the best day to sell (high price) so we get maximum profit

The rule is simple we can't sell without buying, i.e sell should be after buying

lets solve this using both java and dart

Java

public class StockBuyAndSell {
  public static void main(String[] args) {
    int[] prices = new int[] {7, 1, 5, 3, 6, 4};
    int rightIndex=0;
    int min = Integer.MAX_VALUE;
    int maxProfit = 0;
    while(rightIndex<prices.length){
        if(prices[rightIndex]<min){
            min=prices[rightIndex];
        }
        maxProfit = Math.max(maxProfit,prices[rightIndex]-min);
        rightIndex++;
    }
    System.out.println(maxProfit);
  }
}

here we have the stock price list int[] prices = new int[] {7, 1, 5, 3, 6, 4};

lets create an pointer int rightIndex=0, lets create a min with Integer.MAX_VALUE and maxProfit with zero

we are going to iterate the array from the first to last(for loop ,while loop anything is fine), the idea behind this is we need to find the min value in the array and then we will find the difference between the min and current element, and we used Math.Max() to find whether current difference is maximum profit or the previous one and at last we print the maxProfit

Dart

 import 'dart:math';
  void main(){
    List<int> price = [7,1,5,3,6,4];
    int min=double.maxFinite.toInt();
    int maxProfit=0;
    for(int i=0;i<price.length;i++){
      if(min>price[i]){
        min=price[i];
      }
      maxProfit = max(maxProfit, price[i]-min);
    }
    print(maxProfit);
  }

In Dart we don't have min and max values for int so we used double and converted to int

Time Complexity:- O(n)
Auxiliary Complexity:- O(1)

Maximum difference in an array

Ajay k — Sun, 24 Jul 2022 08:42:08 +0000

Today lets look into the maximum difference in an array
problem

find the maximum difference in the array array[j] - array[i],where j>i

we can solve this by using

O(n²) 2 for loop method
O(n) efficient solution

lets look into first one

int maxDif(int[] arr) {
    int maxDif = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] - arr[i] > maxDif) {
          maxDif = arr[j] - arr[i];
        }
      }
    }
    return maxDif;
  }

we are going to create maxDif variable and initialise it with
Integer.MIN_VALUE
next we are going to iterate the array using for loop (i loop)
inside that i loop we are going to iterate all the elements present at the right side only due to the condition j>i we are going to start the j loop with i+1, for each element we are going to find the difference and if the difference is greater than the maxDif we will assign that value to it

Time complexity:- O(n²)

lets look into another method

int maxDifEfficient(int[] arr) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length - 1; i++) {
      max = Math.max(max, arr[i + 1]); 
      min = Math.min(min, arr[i]);
    }
    return max - min;
  }

the logic behind this method is max difference is possible if we subtract between the largest number and the smallest number
so we need to find the largest and smallest number in the array with j>i condition
here we are trying to solve the problem in O(n) for that we are using min and max variables with values Integer.MAX_VALUE, Integer.MIN_VALUE respectively
we iterate the array find which is the max and min value

we find max using Math.max(max,arr[i+1]); here j is i+1 since i+1 is greater than i we satisfy the j>i condition

and we find the min using Math.min(min,arr[i])

once the loop is completed we will have the largest and smallest number in the array with respect to j>i condition and we can subtract that to find the maximum Difference.

Time complexity:- O(n²)

Leaders in an array

Ajay k — Tue, 19 Jul 2022 11:06:01 +0000

To day let's see Leaders in array Problem

An element is leader if it is greater than all the elements to its right side.

we can solve this problem using

two for-loop method(easy)
for-loop method(efficient)

int[] findLeader(int[] arr) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < arr.length; i++) {
      boolean isLeader = true;
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] < arr[j]) {
          isLeader = false;
          break;
        }
      }
      if (isLeader) {
        result.add(arr[i]);
      }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
  }

In This method we are going to traverse the array using i loop
,we are going to check is there any element greater than the element present in the i index by using another for loop j

if we find any element greater than that we don't add that to list if not we add that element to the result

Time Complexity: O(n²)

int[] findLeaderEfficient(int[] arr) {
    List<Integer> result = new ArrayList<>();
    int currentHigh = arr[arr.length - 1];
    result.add(currentHigh);
    for (int i = arr.length - 1; i > 0; i--) {
      if (arr[i] > currentHigh) {
        result.add(arr[i]);
        currentHigh=arr[i];
      }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
  }

The element present at the last of the array will be in the result because we don't have any element at right side to that

we declare currentHigh with the last element value
we move from right to left
we check is the current number is greater than currentHigh
if yes we add that to result list and set that element as currentHigh, if not we move to the next element.

Time Complexity: O(n)

Left Rotate The Array

Ajay k — Mon, 18 Jul 2022 13:26:43 +0000

Today let's see how to left rotate the array

This left rotate question can have say to rotate 1 digit to left or n digit to left lets see both in this post

Left Rotate By 1 Digit
Left Rotate by N Digit

Bonus:- lets look into collections built-in rotate for right and left rotate

lets see left rotate by 1 Digit

int[] reverseTheArrayByOne(int[] arr) {
    int temp = arr[0];
    for (int i = 1; i < arr.length; i++) {
      arr[i - 1] = arr[i];
    }

    arr[arr.length - 1] = temp;
    return arr;
  }

Since we are going to move only one digit we can store the first digit in temp and moving the rest of the elements towards left and we will add the temp to the last index.

Lets see N rotate

We can simply perform N rotate by running the rotate 1 digit N times to get the answer

int[] reverseTheArrayByNTimesEasy(int[] arr, int digits) {
    for (int i = 0; i < digits; i++) {
      arr = reverseTheArrayByOne(arr);
    }
    return arr;
  }

or we can use this method

int[] reverseTheArrayByNDigits(int[] arr, int digits) {
    int[] temp = new int[digits];
    for(int i=0;i<digits;i++){
      temp[i]=arr[i];
    }
    for(int i=0;i<arr.length-digits;i++){
        arr[i]=arr[digits+i];
    }
    for(int i=0;i<temp.length;i++){
        arr[digits-1+i]=temp[i];
    }
    return arr;
  }

To rotate N digits we can make use of temp array to store the N digits and move the remaining digits to the beginning and copy the temp array to the last

Bonus :- we can simply use collections rotate method to perform this array Rotate

int n = 1; 
int[] arr = {2, 5, 8, 9, 12};
    List<Integer> arrList = 
Arrays.stream(arr).mapToObj((e) -> Integer.valueOf(e)).collect(Collectors.toList());
    Collections.rotate(arrList,n);
    System.out.println(arrList.toString());

Here n is the number of digits to be rotated, by default Collections.rotate will perform right rotate to if you want left rotate means you can give negative value.

Collections.rotate(arrList, 1) will perform Right Rotate
Collections.rotate(arrList,-1) Will Perform Left Rotate

Find the Largest Number in the Array

Ajay k — Thu, 14 Jul 2022 12:12:30 +0000

Today let's see how we can find the largest number in the unsorted array

lets see different solution

using two for loops
Using max variable
Using built-in sort

Lets see the two for loop method

int findLargestNumber(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      boolean flag = true;
      for (int j = 0; j < arr.length; j++) {
        if (arr[j] > arr[i]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        return arr[i];
      }
    }
    return -1;
  }

In this we are taking the array as arr
we are going to create a for loop from zero to the length of the array (arr.length)

first in the i loop we are considering the element in the index i as largest element in the array , so we are setting flag to true

now in the j loop we are going to check is there any element greater than the element present in the index i

if its true its going to set the flag false break the loop

since the flag is false it wont enter the if block and the i will be moved to next index this will happen until the i moves to the largest element in the array when i points to the largest element the j loop wont set the flag to false so it will enter if block and will return the largest element

Time complexity O(n²)

Lets now see how we can make this O(n)

int findLargestNumber2(int arr[]) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
      if (max < arr[i]) {
        max = arr[i];
      }
    }
    return max;
  }

In this method we are going to declare a variable max and we initialise it with Integer.MIN_VALUE(-2147483648);

now we just iterate the array with for loop and will check is the current number greater than our max, if true we are going to assign that value to max, when the loop gets over we are returning the max value

Time Complexity:- O(n)

new let's see using built-in sort method

int findLargestNumber3(int[] arr){
    Arrays.sort(arr);
    return arr[arr.length-1];
  }

in this we are using the java built int Arrays.sort() method which will sort us in increasing order so if we need to get the largest element it will present at the last so we are accessing that using arr[arr.length-1],you can also use this method to finding second largest element, first smallest element, second smallest element , n largest or smallest element just by changing the index values

Time Complexity:- O(n log n)

Note:- Arrays.sort() uses As of Java 8, Arrays.sort uses two sorting algorithms. One is a modification of Quicksort named dual-pivot quicksort, the other an adaptation of MergeSort named Timsort. Both have a time complexity of O(n log n)

This is a part of my DSA preparation series
Day 1 to 9 : Analysis of Algorithm
Day 10 : Find the number of digits
Day 11 : Check the given number is palindrome or not
Day 12 : Array basics
Day 13 : Find the Largest Number in the Array

Check the given number is palindrome or not

Ajay k — Sun, 10 Jul 2022 14:18:26 +0000

Today we can see how to solve

Check the given number is palindrome or not

we can solve this using
1. mod method
2. String builder reverse method

A number is palindrome if number and the reverse of given number is same
for 121 the reverse of 121 is again 121 so its palindrome
for 123 the reverse of 123 is 321 321 is not equal to 123
,so it's not palindrome

Mod Method

boolean usingModMethod(int inputNumber) {
    int reverseNumber = 0;
    int temp = inputNumber;
    while (temp > 0) {
      int lastDigit = temp % 10;
      reverseNumber = reverseNumber * 10 + lastDigit;
      temp=temp/10;
    }
    if (reverseNumber == inputNumber) {
      return true;
    }
    return false;
  }

Here we are going to check if the given number is a single digit number because even if we reverse 7 its going to give 7 only so we are checking that

if the number is not a single digit we are going to create a reverseNumber variable with 0 as initial value,Then we create a temp value and assign the input value to it

we create a while loop which is going to check is the given number is greater then Zero(0),if true we are going to enter the while loop
inside the while loop we take the last digit of the given number, so if the input is 121 and we apply mod (%) 10 to 121 it will give the last digit which is 1

121 % 10 => 1 (last digit)

now we multiply the reverseNumber by 10 and we add out last digit

reverseNumber = ( 0 * 10 ) + 1 => 1

now we divide the temp by 10 so 121 becomes 12

NOTE:- Refer Find the number of digits note section to know about divide in java.

now while loop checks is 12 greater than 0 this again enters while loop we get the last digit by mod

12 % 10 => 2 (last digit)

now we multiply the reverseNumber by 10 and we add out last digit

reverseNumber = ( 1 * 10 ) + 2(last digit) => 12

now we divide the temp by 10 so 12 becomes 1, the while loop checks is 1 greater than 0, so this again enters while loop we get the last digit by mod

1 % 10 => 1 (last digit)

now we multiply the reverseNumber by 10 and we add out last digit

reverseNumber = ( 12 * 10 ) + 1(last digit) => 121

now we divide the temp by 10 so 1 becomes 0, so temp is not greater than 0 and wont enter the while loop

we check is the inputNumber is same as reverseNumber if its same we return true else we return false

Using StringBuilder reverse

boolean usingStringBuilder(int inputNumber){
    String str = String.valueOf(inputNumber);
    StringBuilder br = new StringBuilder(str);
    String reverse = br.reverse().toString();
    if(str.equals(reverse)){
      return true;
    }
    return false;
  }

In This we are using to java StringBuilder reverse method to reverse the number and check is it same as inputNumber

NOTE:- Remember to convert string builder to string before compare or else you will get false always even if it same

This is a part of my DSA preparation series
Day 1 to 9 : Analysis of Algorithm
Day 10 : Find the number of digits
Day 11 : Check the given number is palindrome or not

Find the number of digits

Ajay k — Sat, 09 Jul 2022 02:53:25 +0000

To day we are going to look into the basic DSA Problem

Find the number of digits for the given number

let's look how we can solve this problem in different way

we assume all the input given to the program is Greater than Zero and with no leading Zeros for simplicity.

For number with Leading Zeros we have Different Technique which we can see later.

we are going to solve the problem in following methods

Iteration Method
Recursive Method
Using Log10 Method

Let's look into iterative method the most common solution

public int countByIteration(int number) {
    int count = 0;
    while (number > 0) {
      ++count;
      number = number / 10;
    }
    return count;
  }

consider the given input is 123, we have 3 digits
Here we are initialise a variable count to store the number of digits
int count =0;

we have create a while loop which checks is the given number is greater than Zero.

while(number>0){}

123 is greater than Zero, so it enters inside the while loop

Inside the while loop we are incrementing the count value since the number (123) is not Zero (now count=1)

NOTE:- when you divide 2 integers in java 12/10 its 1 not 1.2(result is int), when you divide 2 double in java 12.00/10.00 its 1.2
not 1(result is double) and if you divide one integer and one double 12.00/10 its 1.2(result is double)

we divide the number(123) by 10, which makes 123 to 12

now while loop is going to check is 12 greater than 0 ,since 12 is greater than 0 it again enters the while loop and increment the count value (now count = 2)

we divide the number(12) by 10, which makes 12 to 1

now while loop is going to check is 1 greater than 0 ,since 1 is greater than 0 it again enters the while loop and increment the count value (now count = 3)

we divide the number(1) by 10, which make 1 to 0

now while loop is going to check is 0 greater than 0, since its not true while loop wont execute

after while loop we have the return statement which is going to return the count(count =3)

Time Complexity : O(n) 
Auxiliary Space : O(1)

Now it's time for Recursive Method

  public int countByRecursion(int number) {
    if (number == 0) {
      return 0;
    }
    return 1 + countByRecursion(number / 10);
  }

The base condition is going to check is the number is 0 or not
if its Zero its going to return us 0 and stops the recursive call

if not we are making a recursive call by dividing the number by 10 and adding that call result with 1

Time Complexity : O(log(n)) 
Auxiliary Space : O(log(n))

Now the Log Method

public int countByLog(int number) {
    return (int) Math.floor(Math.log10(number) + 1);
  }

Looks simple right!!! and this is also the efficient method when compared to countByRecursion and countByIteration

the idea behind this is when we do log10(123) its going to give us 2.089905111439398 if we take floor we get 2.0 and then we add 1 to it so it becomes 3.0 at last we cast that to int so it becomes 3

Time Complexity : O(1)
Auxiliary Space : O(1)

If you are at interview you can use the Log method.

This is a part of my DSA preparation series
Day 1 to 9 : Analysis of Algorithm
Day 10 : Find the number of digits