Repository: pandas-dev/pandas

Issue:
BUG: _guess_datetime_format_for_array doesn't guess if first element is '' or 'NaT'
### Pandas version checks

- [X] I have checked that this issue has not already been reported.

- [X] I have confirmed this bug exists on the [latest version](https://pandas.pydata.org/docs/whatsnew/index.html) of pandas.

- [X] I have confirmed this bug exists on the main branch of pandas.


### Reproducible Example

```python
from pandas.core.tools.datetimes import _guess_datetime_format_for_array
print(_guess_datetime_format_for_array(['NaT', '13-01-2000']))  # prints None
print(_guess_datetime_format_for_array(['', '13-01-2000']))  # prints None
```


### Issue Description

Both `'NaT'` and `''` end up becoming `NaT` in `tslib.array_to_datetime`, so they should be ignored when finding the first non-null element to use to guess the datetime format.

However, currently that doesn't happen, because

https://github.com/pandas-dev/pandas/blob/0106c26529900bad0561efb9c9180f7f016365b0/pandas/core/tools/datetimes.py#L129-L131

doesn't exclude `'NaT'` or `''` when looking for the first non-null element

### Expected Behavior

to get
```
%d-%m-%Y
%d-%m-%Y
```

### Installed Versions

<details>


INSTALLED VERSIONS
------------------
commit           : 16d6e095b9cfb7ca33f47a6cdbcbc8f61fd112dc
python           : 3.8.13.final.0
python-bits      : 64
OS               : Linux
OS-release       : 5.10.102.1-microsoft-standard-WSL2
Version          : #1 SMP Wed Mar 2 00:30:59 UTC 2022
machine          : x86_64
processor        : x86_64
byteorder        : little
LC_ALL           : None
LANG             : en_GB.UTF-8
LOCALE           : en_GB.UTF-8

pandas           : 1.6.0.dev0+346.g16d6e095b9
numpy            : 1.23.3
pytz             : 2022.2.1
dateutil         : 2.8.2
setuptools       : 59.8.0
pip              : 22.2.2
Cython           : 0.29.32
pytest           : 7.1.3
hypothesis       : 6.54.6
sphinx           : 4.5.0
blosc            : None
feather          : None
xlsxwriter       : 3.0.3
lxml.etree       : 4.9.1
html5lib         : 1.1
pymysql          : 1.0.2
psycopg2         : 2.9.3
jinja2           : 3.0.3
IPython          : 8.5.0
pandas_datareader: 0.10.0
bs4              : 4.11.1
bottleneck       : 1.3.5
brotli           : 
fastparquet      : 0.8.3
fsspec           : 2021.11.0
gcsfs            : 2021.11.0
matplotlib       : 3.6.0
numba            : 0.56.2
numexpr          : 2.8.3
odfpy            : None
openpyxl         : 3.0.10
pandas_gbq       : 0.17.8
pyarrow          : 9.0.0
pyreadstat       : 1.1.9
pyxlsb           : 1.0.9
s3fs             : 2021.11.0
scipy            : 1.9.1
snappy           : 
sqlalchemy       : 1.4.41
tables           : 3.7.0
tabulate         : 0.8.10
xarray           : 2022.9.0
xlrd             : 2.0.1
xlwt             : 1.3.0
zstandard        : 0.18.0
tzdata           : None
None


</details>



Discussion:

Patch:
diff --git a/pandas/_libs/tslib.pyi b/pandas/_libs/tslib.pyi
index 2212f8db8ea1e..8fec9ecf27f30 100644
--- a/pandas/_libs/tslib.pyi
+++ b/pandas/_libs/tslib.pyi
@@ -16,6 +16,7 @@ def array_with_unit_to_datetime(
     unit: str,
     errors: str = ...,
 ) -> tuple[np.ndarray, tzinfo | None]: ...
+def first_non_null(values: np.ndarray) -> int: ...
 def array_to_datetime(
     values: npt.NDArray[np.object_],
     errors: str = ...,
diff --git a/pandas/_libs/tslib.pyx b/pandas/_libs/tslib.pyx
index a1271ef0d897e..03331f54db892 100644
--- a/pandas/_libs/tslib.pyx
+++ b/pandas/_libs/tslib.pyx
@@ -421,6 +421,23 @@ def array_with_unit_to_datetime(
 
     return oresult, tz
 
+@cython.wraparound(False)
+@cython.boundscheck(False)
+def first_non_null(values: ndarray) -> int:
+    """Find position of first non-null value, return -1 if there isn't one."""
+    cdef:
+        Py_ssize_t n = len(values)
+        Py_ssize_t i
+        int result
+    for i in range(n):
+        val = values[i]
+        if checknull_with_nat_and_na(val):
+            continue
+        if isinstance(val, str) and (len(val) == 0 or val in nat_strings):
+            continue
+        return i
+    else:
+        return -1
 
 @cython.wraparound(False)
 @cython.boundscheck(False)
diff --git a/pandas/core/tools/datetimes.py b/pandas/core/tools/datetimes.py
index 8566468d4e23f..7791ea804a52a 100644
--- a/pandas/core/tools/datetimes.py
+++ b/pandas/core/tools/datetimes.py
@@ -126,9 +126,8 @@ class FulldatetimeDict(YearMonthDayDict, total=False):
 
 def _guess_datetime_format_for_array(arr, dayfirst: bool | None = False) -> str | None:
     # Try to guess the format based on the first non-NaN element, return None if can't
-    non_nan_elements = notna(arr).nonzero()[0]
-    if len(non_nan_elements):
-        if type(first_non_nan_element := arr[non_nan_elements[0]]) is str:
+    if (first_non_null := tslib.first_non_null(arr)) != -1:
+        if type(first_non_nan_element := arr[first_non_null]) is str:
             # GH#32264 np.str_ object
             return guess_datetime_format(first_non_nan_element, dayfirst=dayfirst)
     return None


Test patch:
diff --git a/pandas/tests/tools/test_to_datetime.py b/pandas/tests/tools/test_to_datetime.py
index 2b5457fc9f7b3..263f2b597947a 100644
--- a/pandas/tests/tools/test_to_datetime.py
+++ b/pandas/tests/tools/test_to_datetime.py
@@ -2093,9 +2093,8 @@ def test_to_datetime_dta_tz(self, klass):
 
 
 class TestGuessDatetimeFormat:
-    @td.skip_if_not_us_locale
     @pytest.mark.parametrize(
-        "test_array",
+        "test_list",
         [
             [
                 "2011-12-30 00:00:00.000000",
@@ -2103,11 +2102,14 @@ class TestGuessDatetimeFormat:
                 "2011-12-30 00:00:00.000000",
             ],
             [np.nan, np.nan, "2011-12-30 00:00:00.000000"],
+            ["", "2011-12-30 00:00:00.000000"],
+            ["NaT", "2011-12-30 00:00:00.000000"],
             ["2011-12-30 00:00:00.000000", "random_string"],
         ],
     )
-    def test_guess_datetime_format_for_array(self, test_array):
+    def test_guess_datetime_format_for_array(self, test_list):
         expected_format = "%Y-%m-%d %H:%M:%S.%f"
+        test_array = np.array(test_list, dtype=object)
         assert tools._guess_datetime_format_for_array(test_array) == expected_format
 
     @td.skip_if_not_us_locale