Embedded Files
Palindrome Array
Problem Statement:
You are given an array of size n. The task is to determine if the array is a palindrome. An array is considered a palindrome if the elements read the same forwards and backwards. If the array is a palindrome, print "palindrome", otherwise print "not a palindrome". The program should only traverse half the array to check for palindrome properties.
- Example:
Input:
arr = [2, 3, 5, 5, 3, 2]
Output:
palindromeInput:
arr = [1, 2, 3, 4, 5]
Output:
not a palindrome
class Solution {
public void palindrome_array(int[] arr) {
boolean isPalindrome = true;
for (int i = 0; i < arr.length / 2; i++) {
if (arr[i] != arr[arr.length - 1 - i]) {
isPalindrome = false;
break;
}
}
System.out.println(isPalindrome ? "palindrome" : "not a palindrome");
}
}
public class palindrome {
public static void main(String[] args) {
Solution abc = new Solution();
int[] arr = {2, 3, 5, 5, 3, 2};
abc.palindrome_array(arr);
}
}
The time complexity of the palindrome_array method is O(n/2) = O(n), where n is the length of the input array. This is because the method iterates through half of the array to check for palindrome property.
The space complexity of the palindrome_array method is O(1) because it only uses a constant amount of extra space regardless of the size of the input array.
Reversal Array
Problem Statement: You are given an array of size n. The task is to reverse the elements of the array, meaning that the first element should become the last, the second element should be second-to-last, and so on, until the entire array is reversed.
Example:
Input:
arr = [1, 2, 3, 4, 5]Output:
arr = [5, 4, 3, 2, 1]
class Solution{
public static void reverse(int arr[]){
int ar[]=new int [arr.length];
for(int i=0;i<arr.length;i++){
ar[i]=arr[arr.length-1-i];
System.out.println(ar[i]);
}
}
}
public class ReversalArray{
public static void main(String[] args) {
Solution obj=new Solution();
int ar[]={2,8,9,1,5};
obj.reverse(ar);
}
}
The time complexity of the reverse method in the Solution class is O(n) where n is the number of elements in the input array. This is because the method iterates through the input array once to reverse it.
The space complexity of the reverse method is also O(n) because it creates a new array of the same size as the input array to store the reversed elements.
class Solution{
public static void reverse(int arr[]){
for(int i=0;i<arr.length/2;i++){
int temp=arr[i];
arr[i]=arr[arr.length-1-i];
arr[arr.length-1-i]=temp;
}
for(int k:arr){
System.out.print(k + " ");
}
System.out.println();
}
}
public class ReversalArray{
public static void main(String[] args) {
Solution obj=new Solution();
int ar[]={1,2,4,7,8,3,5};
obj.reverse(ar);
}
}
The time complexity of the reverse method in the Solution class is O(n) where n is the number of elements in the input array. This is because the method iterates through half of the array and swaps elements, resulting in a linear time complexity.
The space complexity is O(1) because the method uses a constant amount of extra space regardless of the size of the input array.
Rotate a Matrix by 90 Degrees Clockwise
Rotate a Matrix by 90 Degrees Clockwise
You are given a 2D matrix of size n x n. Your task is to rotate the matrix by 90 degrees clockwise in place. This means that you should modify the input matrix directly without using any extra space for another matrix.
Example:
Input:
matrix = {
{1, 3, 5, 7},
{3, 4, 6, 8},
{3, 6, 8, 9},
{9, 5, 7, 3}
}
Output:
{
{9, 3, 3, 1},
{5, 6, 4, 3},
{7, 8, 6, 5},
{3, 9, 8, 7}
}
class Solution {
public static void TwoDArray(int arr[][]) {
swap(arr);
reverseRows(arr);
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
static void swap(int arr[][]) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr[0].length; j++) {
int temp = arr[i][j];
arr[i][j] = arr[j][i];
arr[j][i] = temp;
}
}
}
static void reverseRows(int arr[][]) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length / 2; j++) {
int temp = arr[i][j];
arr[i][j] = arr[i][arr[0].length - 1 - j];
arr[i][arr[0].length - 1 - j] = temp;
}
}
}
}
public class RotateMatrix {
public static void main(String[] args) {
Solution obj = new Solution();
int ar[][] = {
{1, 3, 5, 7},
{3, 4, 6, 8},
{3, 6, 8, 9},
{9, 5, 7, 3}
};
obj.TwoDArray(ar);
}
}
The time complexity of the TwoDArray method is O(n^2) where n is the number of rows or columns in the input matrix. This is because we are iterating through each element in the matrix twice - once for swapping and once for reversing rows.
The space complexity is O(1) because we are not using any extra space that grows with the input size. We are only using a constant amount of extra space for temporary variables.
Overall, the algorithm has a time complexity of O(n^2) and a space complexity of O(1).
Page updated
Google Sites
Report abuse