This Tutorial is in continuation of the Previous Tutorial. For Previous Tutorial Visit Array Questions Part-1
Problem -4 Print Bar Charts
Above image shows how the bars output will be show on the screen. Assuming Bar Chart Y Axis represent the Height of the Bar, where Chart X Axis represent the array element value. Based on the output the logic comes in the mind, first we get the max element in the array in the given case 9 is the max element. Then Based on the max element, loop start from max to 1 (so if u see in the image top place to bottom place we place the asterisk (star). As we know the printing always goes from top to bottom and left to right , so we start print from max to 1 and compare this element present in the array so print it.
Step-1 Find the Max Element in the Array
int arr[] = {1,0,2,5,3,7};
int max = arr [0];
for(int element : arr){
if(element>max){
max = element;
}
}
Step-2 Loop From Max to 1 and compare each element from the array element
// For Y - Axis
for(int i = max ; i>=1 ; i--){
// now for the x-axis array elements (Printing a One Row)
for(int j = 0 ; j<arr.length; j++){
if(i <= arr[j]){
System.out.print("*\t");
}
else{
System.out.print("\t");
}
}
System.out.println(); // Moving to the next
}Below is the Full Source Code 👇
public class PrintBarChart {
public static void main(String[] args) {
int arr[] = {1,0,2,5,3,7};
// In bar chart Y (Height) and X Axis (Width)
// So we need to take Height Present from 1 to 7 in Y and in X we need arr values (to represent the bars)
// first get the max height for the bar
int max = arr [0];
for(int element : arr){
if(element>max){
max = element;
}
}
// For Y - Axis
for(int i = max ; i>=1 ; i--){
// now for the x-axis array elements (Printing a One Row)
for(int j = 0 ; j<arr.length; j++){
if(i <= arr[j]){
System.out.print("*\t");
}
else{
System.out.print("\t");
}
}
System.out.println(); // Moving to the next
}
}
}
The Next Question is , Problem - 5 Array is Sorted or Not
Logic is :: if the next element is Smaller than the Previous element so it is not sorted in case of ascending order
if(arr[i]> arr[i+1]){
System.out.println("Not Sorted ");
return;
}
Full Source Code 👇
public class ArrayIsSortedOrNot {
public static void main(String[] args) {
int arr[] = {10,20,30, 40, 50,1};
// Logic is if the next element is Smaller than the Previous so it is not sorted in case of ascending order
for(int i = 0 ; i<arr.length; i++){
if(arr[i]> arr[i+1]){
System.out.println("Not Sorted ");
return;
}
}
System.out.println("Sorted...");
}
}
Problem -6 Reverse an Array Problem
There would be Multiple Approaches to solve this problem. The first approach can be traverse the array from len-1 to 0. and during traverse copy into auxilary array and then copy the orginial array into auxilary array. But this approach Space Complexity will be O(N) and 2 Time Traversal Also required.
The Better Approach would be 2 pointor approach. In this Approach we place the first pointor on 0th index and the second pointor on len-1. And then we keep swapping the value of first with the second and incrementing the first and decrementing the second and we keep doing it till first and second cross each other.
public class ReverseAnArray {
public static void main(String[] args) {
int arr[]= {10,20,30,40,50};
int first = 0;
int last = arr.length-1;
while(first<last){
int temp = arr[first];
arr[first] = arr[last];
arr[last] = temp;
first++;
last--;
}
for(int element: arr){
System.out.print(element+" ");
}
}
}
The TimeComplexity of Above Solution would be n/2 which is O(n) and Space Complexity would be O(1).
Problem-7 Next Question is Pair Sum Problem
Given an Array , find any pair whose sum is equal to K. e.g {2, 9, 4, 3, 1 ,10, 6} K = 9 Output 6,3 e.g K = 5 Output 1, 4
Two Sum Problem LeetCodeApproach - 1 Nested Loop and Do the Sum of 1 and 2 , 1 and 3 , 1 and 4 so on and compare with K But the TC is O(N^2) First loop pick the array first element , and in second loop move to all the element Sum up sum = arr[I] + arr[j] if(sum == k) // sum found , but this approach is N^2
static void approach1() {
int arr[] = {2, 9, 6, 3, 1 ,10, 4};
int k = 9;
int sum = 0;
for(int i = 0; i<arr.length-1; i++) {
for(int j = i+1; j<arr.length;j++) {
sum = arr[i] + arr[j];
if(sum==k) {
System.out.println("Pair is "+arr[i]+" "+arr[j]);
return ;
}
}
}
}Approach-2 Use HashMap to Store the Diff and the Array Element, By Using this Approach we can do in the single Traverse so TC O(N) and SC is O(n)
static void approach2(){
HashMap<Integer, Integer> map = new HashMap<>();
for(int element : arr){
if(map.get(element)== null){
map.put( k - element, element);
}
else{
System.out.println("Pair Sum Found "+map.get(element)+ " "+element);
}
}
}Approach-3 Sort + Two Pointer Approach
static void approach3(){
// Sort the Array and use the Two Pointor Approach
Arrays.sort(arr);
int first = 0;
int last = arr.length-1;
while(first<last){
if((arr[first]+ arr[last])==k){
System.out.println("Pair Sum Found "+arr[first]+" "+arr[last]);
return ;
}
if((arr[first]+arr[last])<k) {
first++;
}
else
if((arr[first]+arr[last])>k) {
last--;
}
}
}Problem-8 Remove Duplicate Element From the Sorted Array.
https://leetcode.com/problems/remove-duplicates-from-sorted-array/. The Solution comes in the mind is Store the Array element in HashSet , so it remove the duplicate element and store it in the list. HashSet is a predefine Java Data Structure , it stores only unique element and it is coming from java.util package. The TC is O(N) and SC is O(N).
The Optimal Solution is compare the previous value 0th index (j pointer) value with the next value (1st index ) (i pointer) , if not equal so increase the j pointer and then the current will consume the next element then increase the ith (next) pointer. Doing it in a loop till reach to the last element. At the end of the loop return the j+1 index. TC is O(N) and SC O(1).
public class RemoveDuplicatesLC09 {
static int removeDuplicates(int[] num) {
int j = 0;
for(int i = 1 ; i<num.length; i++){
if(num[j]!= num[i]){
j++;
num[j] = num[i];
}
}
return j+1;
}
public static void main(String[] args) {
int a[] = {1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,4,4,4,5};
int c = removeDuplicates(a);
for(int i = 0; i<c;i++){
System.out.println("Unique are "+a[i]);
}
}
}Problem-9 Convert array into Zig-Zag fashion.
Given an array of DISTINCT elements, rearrange the elements of array in zig-zag fashion in O(n) time. The converted array should be in form a < b > c < d > e < f.
Input: arr[] = {4, 3, 7, 8, 6, 2, 1}
Output: arr[] = {3, 7, 4, 8, 2, 6, 1}
Input: arr[] = {1, 4, 3, 2}
Output: arr[] = {1, 4, 2, 3}
Approach is loop start to end , then check if the first element is greater than second element so swap it , else if first element is < second element so swap second time
So for this maintain a flag , and compliment every time.
int arr[] = {4, 3, 2, 8, 6, 7, 1};
int temp = 0;
boolean flag = true;
for(int i = 0;i<arr.length-1;i++) {
if(flag) {
if( arr[i]>arr[i+1]) {
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
else {
if( arr[i]<arr[i+1]) {
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
flag = !flag;
}
System.out.println("ZigZag Array is ");
for(int a : arr) {
System.out.println(a);
}
}Problem-10 Find the Leader Element in an Array
Write a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example int the array {300,40,60,90,100,12,16, 17, 4, 3, 5, 2}, leaders are 300,100,17, 5 and 2.
Approach is , Start from the last of array element , and compare last element with the max variable , if the last one is greater than max , so max contains the last element value and then decrease the index and move to the second last element and so on
int arr [] = {16, 17, 4, 3, 5, 2};
int max = 0 ;
for(int i = arr.length-1 ; i>=0; i--) {
if(arr[i]>max) {
System.out.println("Leader "+arr[i]);
max = arr[i];
}
}That's All folks with the tutorial , will meet you with more questions , Happy Coding 😀