ARRAYS
Peak element
class Solution
{
// Function to find the peak element
// arr[]: input array
// n: size of array a[]
public int peakElement(int[] arr,int n)
{
if(n==1)
return 0;
if(arr[0]>=arr[1])
return 0;
if(arr[n-1]>=arr[n-2])
return n-1;
for(int i=1;i<n-1;i++){
if(arr[i]>=arr[i-1]&&arr[i]>=arr[i+1])
return i;
}
return 0;
}
}
Find minimum and maximum element in an array
class Compute
{
static pair getMinMax(long a[], long n)
{
long min = a[0];
long max = a[0];
for (int i = 1; i < n; i++) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > max) {
max = a[i];
}
}
return new pair( min , max );
}
}
Reverse a String
class Reverse
{
// Complete the function
// str: input string
public static String reverseWord(String str)
{
char[] chars=str.toCharArray();
int start=0;
int end=str.length()-1;
while(start<end){
char temp=chars[start];
chars[start]=chars[end];
chars[end]=temp;
start++;
end--;
}
return new String(chars);
}
}
Sort The Array
class Solution
{
int[] sortArr(int[] arr, int n)
{
// code here
Arrays.sort(arr);
return arr;
}
}
Find the Frequency
class Solution{
int findFrequency(int A[], int x){
int count=0;
int n=A.length;
for(int i=0;i<n;i++){
if(A[i]==x){
count++;
}
}
return count;
}
}
Kth smallest element
class Solution{
public static int kthSmallest(int[] arr, int l, int r, int k)
{
//Your code here
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr[k-1];
}
}
Sort an array of 0s, 1s and 2s
class Solution
{
public static void sort012(int a[], int n)
{
// code here
int zero=0,one=0,two=0;
for(int i=0;i<n;i++){
if(a[i]==0) zero++;
if(a[i]==1) one++;
if(a[i]==2) two++;
}
for(int i=0;i<zero;i++) a[i]=0;
for(int i=zero;i<zero+one;i++) a[i]=1;
for(int i=zero+one;i<n;i++) a[i]=2;
}
}
Move all negative elements to end
class Solution {
public void segregateElements(int arr[], int n)
{
// Your code goes here
int[] temp = new int[n]; // create a temporary array to store the sorted elements
int j = 0; // index of the first negative element
for (int i = 0; i < n; i++) {
if (arr[i] >= 0) { // if the current element is positive or zero, store it in the temporary array
temp[j] = arr[i];
j++;
}
}
j = n-1; // reset the index of the first negative element
for (int i = n-1; i >= 0; i--) {
if (arr[i] < 0) { // if the current element is negative, store it in the temporary array
temp[j] = arr[i];
j--;
}
}
for (int i = 0; i < n; i++) { // copy the elements from the temporary array back to the original array
arr[i] = temp[i];
}
}
}
Union of two arrays
class Solution{
public static int doUnion(int a[], int n, int b[], int m)
{
//Your code here
Set<Integer> union=new HashSet<>();
for(int i=0;i<n;i++){
union.add(a[i]);
}
for(int i=0;i<m;i++){
union.add(b[i]);
}
return union.size();
}
}
Cyclically rotate an array by one
class Compute {
public void rotate(int arr[], int n)
{
int temp=arr[n-1];
for(int i=n-1;i>0;i--){
arr[i]=arr[i-1];
}
arr[0]=temp;
}
}
Count pairs with given sum
class Solution {
int getPairsCount(int[] arr, int n, int k) {
// code here
Map<Integer,Integer> freq=new HashMap<>();
int pairs=0;
for(int i=0;i<n;i++){
int complement=k-arr[i];
if(freq.containsKey(complement)){
pairs+=freq.get(complement);
}
freq.put(arr[i],freq.getOrDefault(arr[i],0)+1);
}
return pairs;
}
}
Find duplicates in an array
class Solution {
public static ArrayList<Integer> duplicates(int arr[], int n) {
// code here
ArrayList<Integer> result=new ArrayList<>();
for(int i=0;i<n;i++){
int index=arr[i]%n;
arr[index]+=n;
}
for(int i=0;i<n;i++){
if((arr[i]/n)>1){
result.add(i);
}
}
if(result.isEmpty()){
result.add(-1);
}
return result;
}
}
Subarray with given sum
class Solution
{
//Function to find a continuous sub-array which adds up to a given number.
static ArrayList<Integer> subarraySum(int[] arr, int n, int s)
{
// Your code here
int left = 0;
int right = 0;
int sum = 0;
while (right < n) {
sum += arr[right];
while (sum > s) {
sum -= arr[left];
left++;
}
if (sum == s) {
ArrayList<Integer> result = new ArrayList<>();
result.add(left + 1); // 1-based indexing
result.add(right + 1); // 1-based indexing
return result;
}
right++;
}
ArrayList<Integer> result = new ArrayList<>();
result.add(-1); // No subarray found
return result;
}
}
Missing number in array
class Solution {
int missingNumber(int array[], int n) {
// Your Code Here
int totalSum = (n * (n + 1)) / 2; // Calculate the sum of all integers from 1 to N
int arraySum = 0;
// Calculate the sum of all elements in the array
for (int i = 0; i < n - 1; i++) {
arraySum += array[i];
}
return totalSum - arraySum; // Return the missing element
}
}
Common elements
class Solution
{
ArrayList<Integer> commonElements(int A[], int B[], int C[], int n1, int n2, int n3)
{
// code here
ArrayList<Integer> result = new ArrayList<Integer>();
int i = 0, j = 0, k = 0;
int prev = Integer.MIN_VALUE;
while (i < n1 && j < n2 && k < n3) {
if (A[i] == B[j] && B[j] == C[k]) {
if (A[i] != prev) {
result.add(A[i]);
prev = A[i];
}
i++;
j++;
k++;
}
else if (A[i] < B[j])
i++;
else if (B[j] < C[k])
j++;
else
k++;
}
return result;
}
}
Subarrays with equal 1s and 0s
class Solution
{
//Function to count subarrays with 1s and 0s.
static int countSubarrWithEqualZeroAndOne(int arr[], int n)
{
// add your code here
HashMap<Integer,Integer> map=new HashMap<>();
int count=0;
int sum=0;
for(int i=0;i<n;i++){
if(arr[i]==0){
sum+=-1;
}else{
sum+=1;
}
if(sum==0){
count+=1;
}
if(map.containsKey(sum)){
count+=map.get(sum);
map.put(sum,map.get(sum)+1);
}else{
map.put(sum,1);
}
}
return count;
}
}
Kadane's Algorithm
class Solution{
// arr: input array
// n: size of array
//Function to find the sum of contiguous subarray with maximum sum.
long maxSubarraySum(int arr[], int n){
// Your code here
int bestsum=Integer.MIN_VALUE;
int currentsum=0;
for(int i=0;i<n;i++){
currentsum=Math.max(arr[i],currentsum+arr[i]);
bestsum=Math.max(bestsum,currentsum);
}
return bestsum;
}
}
Comments
Post a Comment