Two Pointer Technique In Arrays

In general we will iterate the array using one pointer starting from the first element and ending at the last element.

Sometimes we need two pointers at the same time one pointer from starting element and the other element from the last element.


Example :

Reverse the Array :


Here we will swap the first element with last one until it reaches the middle position.


We use two pointers at the same time to do the iteration :

One starts from the first element and the other pointer starts from the last element .

Swapping takes places until the two pointers meet each other.

package com.techyield.operationsinarray;

public class ReverseArrayUsingTwoPointers {

public static void main(String[] args) {

int a[] = {1,2,3,4,5,6,7,8,9,10};

int i = 0;

int j = a.length-1;

int temp = 0;

while(i<j) {

temp = a[i];

a[i] = a[j];

a[j] = temp;

i++;

j--;

}

for(int b : a)

System.out.print(" "+b);

}

}

Output :

 10 9 8 7 6 5 4 3 2 1

NOTE:

Scenarios where you need to use two-pointer technique:

1. Iterate the array from two ends to middle.

2. One pointer starts from the beginning while the other pointer starts from the end.

So this technique often we use in sorted array .

StringBuilder - Java

String Builder :


String Builder is often used if you want use string concatenation very often.


Time complexity will be O(N).

package com.techyield.operationsinarray;

public class StringBuilder {

public static void main(String[] args) {

int n = 10000;

StringBuilder str = new StringBuilder("Hello");

for(int i =0 ; i < n ; i++) {

str.append("satya");

}

String s = str.toString();

}

}

Immutable String - Problem and Solutions

In C++ String is mutable , So there won't be any Problem.

But in Java String is immutable which creates problem and we have to resolve it .

So as String is immutable , If you want to change to change the String you have to create a new String even if you want to change one character .


So if we have to do String Concatenation in Java using '+' . It will take O(N*N) time .

String Concatenation is Slow in Java compared to C++ Which is not noticeable .

In Java Concatenation happens by first allocating enough space for new string and copy the contents from old string and append to the new String.

Time Complexity for a String of length 10 and n = 10000 is :


10+10* 2 +10 * 3 + ...... + 10 * n

= 10 * n * (n+1) / 2

Which will be O(N*N).

Example :

package com.techyield.operationsinarray;

public class StringConcatenation {

public static void main(String[] args) {

String s = "";

int n = 200000;

for(int i =0 ; i< n ;i++) {

s += "hello";

}

}

}

So you want to make String Immutable to Mutable :

Check here : https://techyield.blogspot.com/2019/06/string-immutable-to-mutable-java.html

String Immutable to Mutable (Java) Solutions

If you want your string to covert from Immutable to Mutable then better solution is :

Convert the String to CharArray :

package com.techyield.operationsinarray;

public class StringCharArray {

public static void main(String[] args) {

String s1 ="Sunny G";

char[] array = s1.toCharArray();

array[5] = ',';

System.out.println(array);

}

}

String Operations

String Operations :


Concatenation using '+'.


Position of First 'o' using indexOf().

Position of LastIndex of 'o' using lastIndexOf().

Getting Substring in a String using substring method substring(beginIndex , endIndex);

Example :


/**
 *
 */
package com.techyield.operationsinarray;

public class StringModification {

/**
* @param args
*/
public static void main(String[] args) {

String s1 = "Sunny";
s1+=" G";

System.out.println(s1);

System.out.println("The index of first n : "+s1.indexOf('n'));
System.out.println("The index of last n :"+s1.lastIndexOf('n'));

// Substring

System.out.println(s1.substring(2,7));
}

}

Output :

Sunny G

The index of first n : 2

The index of last n :3

nny G

Notes:

We should be aware of the time complexity of built in operations.

If the length of the string is N , the time complexity of both finding and substring operation is O(N).

Never forget the time complexity of the built-in operations into consideration when you are finding the time complexity of your solution.

String Immutable Or Mutable

Immutable means that we can't change the content of the String once it is initialized.

1. In C++ String is Mutable . Which means you can modify the String just like array.

2. In Java String is Immutable. Which will create problems so many problems , we can resolve with the help of converting String to CharArray or Using StringBuilder .

Testing on String By Modifying It :

/**
 *
 */
package com.techyield.operationsinarray;

/**
 * @author satyanarayanagokavarapu
 *
 */
public class StringModification {

/**
* @param args
*/
public static void main(String[] args) {

String s1 = "Sunny";

s1[4]=','; // It will show compile Time Error as This type of expression can be array type //can be resolved to String .

System.out.println(s1);

}

}

Introduction To String

String :

A String is an array of Unicode Characters. But like Array we can perform all the operations on String .

But there are some differences based on programming language.

Operations&Functions On Strings :

Compare Function :

String has its own compare function.

"==" Can be used in Java to compare whether the two objects are same but cannot be used to compare two Strings.

"==" Can be used in C++ to Compare Two Strings as it supports Operator Overloading.


Example :

package com.techyield.operationsinarray;

public class OperationsInString {

public static void main(String[] args) {

String s1 = "Hello World! Chitti Version 2.0";

// s2 is reference of s1

String s2 = s1;

// s3 is copy of s1

String s3 = new String(s1);

System.out.println("s1 is \""+s1+"\"");

System.out.println("s2 is "+s2);

System.out.println("s3 is "+s3);

// compare using ==

System.out.println("Compare Strings using \"==\"");

System.out.println("Comparing s1 and s2"+ (s1==s2));

System.out.println("Comparing s2 and s3 using \"==\""+ (s2==s3));

System.out.println("Comparing s1 and s3 using \"==\""+ (s1==s3));

// compare using equals method

System.out.println("Compare Strings using equals method");

System.out.println("Comparing s1 and s2"+ (s1.equals(s2)));

System.out.println("Comparing s2 and s3 using \"==\""+ (s2.equals(s3)));

System.out.println("Comparing s1 and s3 using \"==\""+ (s1.equals(s1)));

// compare using compareTo method

System.out.println("Compare Strings using compareTo method");

System.out.println("Comparing s1 and s2"+ (s1.compareTo(s2) == 0));

System.out.println("Comparing s2 and s3 using \"==\""+ (s2.compareTo(s3) == 0));

System.out.println("Comparing s1 and s3 using \"==\""+ (s1.compareTo(s1) == 0));

}

}